The minimum rank of matrices and the equivalence class graph (Q2459958)

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. \]