The Triangle Size of Zero-nonzero Patterns

• 作者: Gufang Mou
• 来源期刊: 数学计算：中英文版
• 学科: 数学
• 关键词: Zero-Nonzero Pattern TRIANGLE SIZE BIPARTITE GRAPH
• 年，卷（期）: 2015,（3）
• 页码范围: 56-59
• 页数: 4页
• 分类号: O1

摘要

For an asymmetric matrix,the zero-nonzero pattern P of entries can be described by a digraphΓ(P)which has an arc if an entry is nonzero.The minimum rank of a zero-nonzero pattern is defined to be the smallest possible rank over all real matrices having the given zero-nonzero pattern.Definitions of various graph parameters that have been used to bound minimum rank of a zerononzero pattern,including path cover number and edit distance,and the triangle size tri(P).In this paper,by converting a digraph into an undirected bipartite graph G(U,V),we present an algorithm for constructing a sub-bipartite graph with the unique maximum perfect matching M',and obtain that tri(P)=|M'|for P.