Three-connected graphs whose maximum nullity is at most three (Q929488): Difference between revisions

Let \(G=(V,E)\) be a graph with \(V=\{1,2,\dots,n\}\). Define \(\mathcal S(G)\) as the set of all \(n\times n\) real-valued symmetric matrices \(A=[a_{i,j}]\) with \(a_{i,j}\neq 0\), \(i\neq j\), if and only if \(ij\in E\). The maximum nullity of \(G\), denoted by \(M(G)\), is the largest possible nullity of any matrix \(A\in\mathcal S(G)\). If we denote by \(mr(G)\) the smallest possible rank of any matrix \(A\in\mathcal S(G)\), then \(M(G)+mr(G)=n\). In this paper it is proved that \(k\)-connected graphs \(G\) have \(M(G)\geq k\) and that \(k\)-connected partial \(k\)-paths \(G\) have \(M(G)=k\). For \(3\)-connected graphs \(M(G)=3\) if and only if \(G\) is a partial \(3\)-path.