An Algorithm to Analyse the Polynomial Deck of the Line Graph of a Triangle-free Graph

Abstract

An algorithm is presented in which a polynomial deck, $\mathcal{P}D$, consisting of $m$ polynomials of degree $m-1$, is analysed to check whether it is the deck of characteristic polynomials of the one-vertex-deleted subgraphs of the line graph, $H$, of a triangle-free graph, $G$. We show that if two necessary conditions on $\mathcal{P}D$, identified by counting the edges and triangles in $H$, are satisfied, then one can construct potential triangle-free root graphs, $G$, and by comparing the polynomial decks of the line graph of each with $\mathcal{P}D$, identify the root graph.