GRAPHS WHOSE MINIMAL RANK IS TWO

By Wayne W. Barrett, H. Holst, Raphael Loewy. 2004

107 citations recorded by the source corpus.

Let F be a field, G =( V, E) be an undirected graph on n vertices, and let S(F, G) be the set of all symmetric n × n matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. For example, if G is a path, S(F, G )co nsists of the symmetric irreducible tridiagonal matrices. Let mr(F, G) be the minimum rank over all matrices in S(F, G). Then mr(F, G) = 1 if and only if G is the union of a clique with at least 2 vertices and an independent set. If F is an infinite field such that charF � , then mr(F, G) ≤ 2i f and only if the complement of G is the join of a clique and a graph that is the union of at most two cliques and any number of complete bipartite graphs. A similar result is obtained in the case that F is an infinite field with char F = 2. Furthermore, in each case, such graphs are characterized as those for which 6 specific graphs do not occur as induced subgraphs. The number of forbidden subgraphs is reduced to 4 if the graph is connected. Finally, similar criteria is obtained for the minimum rank of a Hermitian matrix to be less than or equal to two. The complement is the join of a clique and a graph that is the union of any number of cliques and any number of complete bipartite graphs. The number of forbidden subgraphs is now 5, or in the connected case, 3.

Subfields: Computational Theory and Mathematics, Electrical and Electronic Engineering, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/529fcb9fe5bb91829cb327c91f7db4283f797db9

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Electrical and Electronic Engineering

In Geometry and Topology

Citations in the corpus

Minimum Rank Problems (2010, unknown): “AMS Classification 05C05, 15A03, 15A18”
SPECTRAL GRAPH THEORY AND THE INVERSE EIGENVALUE PROBLEM OF A GRAPH (2005, background): “Additional characterizations of graphs having minimum rank 2 can be found in [4].”
On the minimum rank of not necessarily symmetric matrices : a preliminary study (2009, methodology): “The triangle number has been used as a lower bound for minimum rank in both the symmetric and asymmetric minimum rank problems, see e.g., [2], [4], [8].”
Positive semidefinite zero forcing (2013, methodology): “4 below, which characterizes high positive semidefinite zero forcing number, follows 236 from the characterization of graphs having mr+(G) ≤ 2 in [7], using the parameter mz+ and the 237 next proposition.”
An upper bound for the minimum rank of a graph (2008, background): “By [4], any graph having mr(S G ) > 2 over an infinite field F must have one of these subgraphs as an induced subgraph, so mr(S G ) ≤ 2.”
A variant on the graph parameters of Colin de Verdiere: Implications to the minimum rank of graphs (2005, background): “Further it is well known that for any connected graph G on n vertices that mr(G) = 1 if and only if G is Kn. Fiedler [8] established that mr(G) = n− 1 if and only if G is Pn. Barrett, van der Holst, and Loewy [4] have characterized all of the graphs on n vertices that satisfy mr(G) = 2.”