ON THE NORMALISED LAPLACIAN SPECTRUM, DEGREE-KIRCHHOFF INDEX AND SPANNING TREES OF GRAPHS

By Jing Huang, Shuchao Li. Bulletin of the Australian Mathematical Society, 2015

74 citations recorded by the source corpus.

Given a connected regular graph $G$, let $l(G)$ be its line graph, $s(G)$ its subdivision graph, $r(G)$ the graph obtained from $G$ by adding a new vertex corresponding to each edge of $G$ and joining each new vertex to the end vertices of the corresponding edge and $q(G)$ the graph obtained from $G$ by inserting a new vertex into every edge of $G$ and new edges joining the pairs of new vertices which lie on adjacent edges of $G$. A formula for the normalised Laplacian characteristic polynomial of $l(G)$ (respectively $s(G),r(G)$ and $q(G)$) in terms of the normalised Laplacian characteristic polynomial of $G$ and the number of vertices and edges of $G$ is developed and used to give a sharp lower bound for the degree-Kirchhoff index and a formula for the number of spanning trees of $l(G)$ (respectively $s(G),r(G)$ and $q(G)$).

Subfields: Discrete Mathematics and Combinatorics, Geometry and Topology, Organic Chemistry

View Paper: https://www.semanticscholar.org/paper/aea8ad54b83849141bb27602c956e41c80906bd3