Adding an edge to a graph can push a quantity tied to its line graph past a threshold. The paper gives a condition that prevents that jump, and proves the condition survives two ways of growing the graph: splitting an edge into four, and attaching a module at any vertex. Starting from a pentagon, this builds an infinite family of graphs sitting exactly on the bound. The condition is enough, but it is not known to be necessary, and the general bound stays open.
For two families of graphs, roses and generalized theta graphs, the work computes in closed form how many eigenvalues of the line graph are positive, zero and negative. The result depends only on the lengths of the paths, counted modulo four.
Research seriesVersion 2.0-rev2 · current revision of Version 2
Not one isolated counterexample but an infinite family, inside a class of very simple graphs, with the means to carry the result from one graph to another and exact certificates for every case.
An upper bound that holds for every graph, constructions that reach it, and counterexamples to a simplification that looked natural. Every case is checked with exact arithmetic, not approximation.
