The minimum rank of matrices and the equivalence class graph
The paper deals with the minimum rank of matrices associated with an undirected connected graph. For a given undirected connected graph \(G=(V(G),E(G))\), the minimum rank of \(G\), \(hmr(G)\), (the real symmetric minimum rank of \(G\), \(mr(G)\)) is defined to be the smallest possible rank over all hermitian (real symmetric) matrices associated with \(G\), that is, matrices \(A\) whose \((i,j)\)th entry is non-zero if and only if \(i \neq j\) and \(\{i,j\}\) is an edge in \(G\). For each vertex \(x\) in \(G\), \(N(x)\) is the set of all neighbors of \(x\). Let \(R\) be the equivalence relation on \(V(G)\) such that \[ \forall x,y \in V(G) \;\;xRy \Leftrightarrow N(x)=N(y). \] Let \(G=(V(G),E(G))\) be a graph and \(X_1, \dots, X_p\) be the equivalence classes for the relation \(R\). The equivalence class graph of \(G\) is defined as the graph \({\mathcal G}=(V({\mathcal G}),E({\mathcal G}))\) where \(V({\mathcal G})=\{X_1,\dots,X_p\}\) and \(\{X_i,X_j\}\in E(\mathcal{G})\) if, and only if, there exist \(x \in X_i\) and \(y \in X_j\) such that \(\{ x,y\}\) is an edge in \(G\). The authors study classes of undirected connected graphs \(G=(V(G),E(G))\), such that the minimum rank of \(G\) is equal to the number of equivalence classes for the relation \(R\) on \(V(G)\), \(| V(G)/R| \). Specifically, they show the following main result: Let \(G=(V(G),E(G))\) be a graph such that the equivalence class graph \({\mathcal G}\) is the path \(X_1,\dots,X_p\). Then, \[ hmr(G)=mr(G)=| V(G)/R| =p \] if, and only if, \(p\) is even and there do not exist \(i,j\) with \(1 \leq i<j \leq p\) such that \(i\) is odd, \(j\) is even and \(| X_i| =| X_j| =1\). When this is not the case \[ hmr(G)=mr(G)=p-1. \]
- A variant on the graph parameters of Colin de Verdiere: Implications to the minimum rank of graphs
- Computation of minimal rank and path cover number for certain graphs
- Forbidden minors for the class of graphs G with (G) 2
- Graphs whose minimal rank is two
- Graphs whose minimal rank is two: The finite fields case
- Matrix Analysis
- On the difference between the maximum multiplicity and path cover number for tree-like graphs
- On the Eigenvalues and Eigenvectors of a Class of Matrices
- On the maximum multiplicity of an eigenvalue in a matrix whose graph contains exactly one cycle
- On the minimum rank of the join of graphs and decomposable graphs
- Problems in algebraic combinatorics
- Spectral graph theory and the inverse eigenvalue problem of a graph
- Spectral multiplicity and splitting results for a class of qualitative matrices
- The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree
- Minimum rank of matrices described by a graph or pattern over the rational, real and complex numbers
- Some mixed graphs with \(H\)-rank 4, 6 or 8
- Minimum-rank matrices with prescribed graph
- On the minimum vector rank of multigraphs
- Graphs whose adjacency matrices have rank equal to the number of distinct nonzero rows
- Theta rank, levelness, and matroid minors
- Determining the minimum rank of matroids whose basis graph is common
- On upper bounds for the minimum rank of regular classes of (0,1)-matrices
- A note on universally optimal matrices and field independence of the minimum rank of a graph
This page was built for publication: The minimum rank of matrices and the equivalence class graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2459958)
