The maximum number of Parter vertices of acyclic matrices (Q2214046)

This manuscript deals with the maximum number of Parter vertices of a singular symmetric matrix whose underlying graph is a tree. In this paper, all graphs are assumed to be finite, undirected and without loops or multiple edges. Let \(G\) be a graph with vertex set \(V(G)\) and edge set \(E(G)\). \(S_F(G)\) denotes the set of all the symmetric matrices \(A\) with entries in the field \(F\), whose rows and columns are indexed by \(V(G)\), such that for every two distinct vertices \(u, v \in V(G)\), the \((u,v)\)-entry of \(A\) is nonzero if and only if \((u,v) \in E(G)\). The adjacency matrix of \(G\), \(\mathcal{A}(G)\), is a \((0,1)\)-matrix in \(S_F(G)\) all of whose diagonal entries are equal \(0\). In fact, the matrices in \(S_F(G)\) can be seen as weighted adjacency matrices of \(G\). For any tree \(T\), the elements of \(S_F(T)\) are referred as acyclic matrices. For every matrix \(A \in S_F(G)\) and subset \(X\) of \(V(G)\), the principal submatrix of \(A\) obtained by deleting the rows and columns indexed by \(X\) is denoted by \(A(X)\). Let \(G\) be a graph with \(n=|V(G)|\) and let \(A \in S_F(G)\). A vertex \(v \in V(G)\) is a Parter vertex of \(A\) if \(\eta(A(v))=\eta(A)+1\), where \(\eta(A)\) denotes the dimension of \(\ker{A}\). In this paper, the authors are interested in the maximum number of Parter vertices of singular acyclic matrices. It is known that this number, for a singular matrix with rank \(r\) whose underlying graph has no isolated vertices, is at most \(r-1\). In addition, the maximum number of Parter vertices of \(n \times n\) singular acyclic matrices is \(2\lfloor\frac{n-1}{2}\rfloor-1\). As a generalization, the authors prove that the number of Parter vertices of singular acyclic matrices with rank \(r\) is at most \(2\lfloor\frac{r}{2}\rfloor-1\). They also characterize the structure of trees which achieve this upper bound.