×

On the maximum positive semi-definite nullity and the cycle matroid of graphs. (English) Zbl 1173.05031

Summary: Let \(G=(V,E)\) be a graph with \(V=\{1,2,\dots,n\}\), in which we allow parallel edges but no loops, and let \({\mathcal S}_+(G)\) be the set of all positive semi-definite \(n\times n\) matrices \(A=[a_{i,j}]\) with \(a_{i,j}=0\) if \(i\neq j\) and \(i\) and \(j\) are non-adjacent, \(a_{i,j}\neq 0\) if \(i\neq j\) and \(i\) and \(j\) are connected by exactly one edge, and \(a_{i,j}\in\mathbb R\) if \(i=j\) or \(i\) and \(j\) are connected by parallel edges. The maximum positive semi-definite nullity of \(G\), denoted by \(M_+(G)\), is the maximum nullity attained by any matrix \(A\in{\mathcal S}_+(G)\). A \(k\)-separation of \(G\) is a pair of subgraphs \((G_1,G_2)\) such that \(V(G_1)\cup V(G_2)=V\), \(E(G_1)\cup E(G_2)=E\), \(E(G_1)\cap E(G_2)=\emptyset\) and \(|V(G_1)\cap V(G_2)|=k\). When \(G\) has a \(k\)-separation \((G_1,G_2)\) with \(k\leq 2\), we give a formula for the maximum positive semi-definite nullity of \(G\) in terms of \(G_1,G_2\), and in case of \(k=2\), also two other specified graphs. For a graph \(G\), let \(c_G\) denote the number of components in \(G\). As a corollary of the result on \(k\)-separations with \(k\leq 2\), we obtain that \(M_+(G)- c_G= M_+(G')-c_{G'}\) for graphs \(G\) and \(G'\) that have isomorphic cycle matroids.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A18 Eigenvalues, singular values, and eigenvectors
05B35 Combinatorial aspects of matroids and geometric lattices
PDFBibTeX XMLCite
Full Text: DOI EuDML EMIS Link