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

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.