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, '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 sub graphs of the line graph, H, of a triangle-free graph, G. We show that if two necessary conditions on '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 'P D, identify the root graph.