标题： cobipartite图的最小秩问题参数之间的关系 显示英文标题

标题： Relationships between minimum rank problem parameters for cobipartite graphs

摘要： 对于一个简单图，最小秩问题是确定在非对角线非零元素出现在与图的边相对应的位置的对称矩阵中的最小秩。 关于这个最小秩（以及等价值，最大零空间维数）的界限由各种图参数给出，最著名的是零强迫数及其变体。 对于一个矩阵，将每个非零元素替换为符号\(\ast\)就得到了它的零-非零模式。 与之相关的最小秩问题是，在仅知道该模式的情况下，确定矩阵的最小可能秩。 这个最小秩的最基本下界是该模式的三角形数。 一个cobipartite图是bipartite图的补图；其顶点可以划分为两个团。 这样的图以自然的方式对应于一个零-非零模式。 在无限域上，图的最小秩和该模式的最小秩遵循一个简单的关系。 我们证明了该关系同样适用于图的零强迫数和模式的三角形数。 这对两个最小秩问题之间的关系有影响。 我们还探讨了对于cobipartite图，零强迫数的变体和其他对最小秩问题重要的参数之间的关系，以及对于一般图，这些参数如何根据与图相关联的对称矩阵的零-非零模式来解释。 显示英文摘要

摘要： For a simple graph, the minimum rank problem is to determine the smallest rank among the symmetric matrices whose off-diagonal nonzero entries occur in positions corresponding to the edges of the graph. Bounds on this minimum rank (and on an equivalent value, the maximum nullity) are given by various graph parameters, most notably the zero forcing number and its variants. For a matrix, replacing each nonzero entry with the symbol \(\ast\) gives its zero-nonzero pattern. The associated minimum rank problem is to determine, given only this pattern, the smallest possible rank of the matrix. The most fundamental lower bound on this minimum rank is the triangle number of the pattern. A cobipartite graph is the complement of a bipartite graph; its vertices can be partitioned into two cliques. Such a graph corresponds to a zero-nonzero pattern in a natural way. Over an infinite field, the minimum rank of the graph and that of the pattern obey a simple relationship. We show that this same relationship is followed by the zero forcing number of the graph and the triangle number of the pattern. This has implications for the relationship between the two minimum rank problems. We also explore how, for cobipartite graphs, variants of the zero forcing number and other parameters important to the minimum rank problem are related, as well as how, for graphs in general, these parameters can be interpreted in terms of the zero-nonzero patterns of the symmetric matrices associated with the graph.