Academic Editor: Youssef EL FOUTAYENI
Received |
Accepted |
Published |
03 February 2020 |
18 February 2020 |
10 March 2020 |
Abstract: The idiosyncratic polynomial of a graph G with adjacency matrix A is the characteristic polynomial of the matrix A + y(J − A − I), where I is the identity matrix and J is the all-ones matrix. It follows from a theorem of Hagos (2000) combined with an earlier result of Johnson and Newman (1980) that the idiosyncratic polynomial of a graph is reconstructible from the multiset of the idiosyncratic polynomial of its vertex-deleted subgraphs. For a digraph G with adjacency matrix A, we define its idiosyncratic polynomial as the characteristic polynomial of the matrix A + y(J − A − I) + zAt . By forbidding two fixed digraphs on three vertices as induced subdigraphs, we prove that the idiosyncratic polynomial of a digraph is reconstructible from the multiset of the idiosyncratic polynomial of its induced subdigraphs on three vertices. As an immediate consequence, the idiosyncratic polynomial of a tournament is reconstructible from the collection of its 3-cycles. Another consequence is that all the transitive orientations of a comparability graph have the same idiosyncratic polynomial.
