On the nullity of middle graphs

The nullity of a graph is the multiplicity of \(0\) as an eigenvalue of its adjacency matrix. Classifying connected graphs with a given nullity is a difficult problem. \textit{I. Gutman} and \textit{I. Sciriha} [Discrete Math. 232, No. 1--3, 35--45 (2001; Zbl 0971.05070)] showed that, although the nullity of connected line graphs is unbounded, the case of line graphs of trees is simpler, with all such graphs having nullity \(0\) or \(1\). The main contribution of this paper is that the middle graph \(M(G)\) of a connected graph \(G\) also has nullity either \(0\) or \(1\), with the latter case arising if and only if \(G\) is bipartite. The middle graph \(M(G)\) is the graph with vertex set \(V(G)\cup E(G)\), and edges corresponding to pairs \((e,e^\prime)\) of incident edges of \(G\) and to pairs \((v,e)\) where \(v\) is a vertex of \(G\) and \(e\) is an edge it meets.\N\NThe proof of this result uses an expression for the adjacency matrix of \(M(G)\) in terms of the incidence matrix of \(G\) and the adjacency matrix of the line graph \(L(G)\), related expressions for the adjacency matrix of \(L(G)\) and the signless Laplacian matrix of \(G\) in terms of the incidence matrix of \(G\), and facts about the characteristic polynomial of the signless Laplacian. An application is given to honeycomb silicate networks, which have previously been studied in various contexts. As these arise as middle graphs of toroidal hexagonal lattices, it follows that they have nullity \(1\).

Cites work

This page was built for publication: On the nullity of middle graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7018429)