Line-graph inertia of roses and generalized theta graphs

Abstract

For a graph G, the adjacency inertia of the line graph L(G) is determined by the number of eigenvalues of the signless Laplacian Q(G) above, equal to, and below 2. The manuscript computes the inertia of Q(G) − 2I, and hence the inertia of the adjacency matrix of L(G), exactly, including every singular case, for rose graphs and generalized theta graphs. Both computations follow from a common reduction: deleting the common vertices leaves disjoint paths, and range-kernel elimination leaves their singular kernel directions and a residual scalar for a rose graph, or a 2 by 2 matrix for a generalized theta graph. The resulting formulas depend only on the path lengths modulo 4. Consequences include the bound m_Q(G,2) ≤ c(G) for generalized theta graphs with at least three paths and an exact comparison with the conjectured bound 2s(L(G)) ≤ c(G) + 1, whose slack grows linearly with the cyclomatic number on both classes, with equality only for cycles whose length is congruent to 1 modulo 4. The general conjecture is not proved. A partial extension to bridgeless cacti is also given, and exact finite computations check every formula branch.