On the spectral reconstruction problem for digraphs

MaRDI QIDQ6328191FDO

Authors Edward Bankoussou-mabiala, Abderrahim Boussaïri, Abdelhak Chaïchaâ, Brahim Chergui, Soufiane Lakhlifi

Publication date 30 October 2019

Mathematics Subject Classification ID

Graph polynomials (05C31) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

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)+z{A}^T$. 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.

This page was built for publication: On the spectral reconstruction problem for digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6328191)