Distinguishing graphs by their spectra, Smith normal forms and complements

The search for a highly discriminating and easily computable invariant to distinguish graphs remains a challenging research topic. Here we focus on cospectral graphs whose complements are also cospectral (generalized cospectral), and on coinvariant graphs (same Smith normal form) whose complements are also coinvariant (generalized coinvariant). We show a new characterization of generalized cospectral graphs in terms of codeterminantal graphs. We also establish the Smith normal form of some graph classes for certain associated matrices, and as an application, we prove that the Smith normal form can be used to uniquely determine star graphs. Finally, for graphs up to 10 vertices, we present enumeration results on the number of generalized cospectral graphs and generalized coinvariant graphs with respect to several associated matrices.

Recommended citation: Aida Abiad, Carlos A. Alfaro and Ralihe R. Villagrán. "Distinguishing graphs by their spectra, Smith normal forms and complements." Applied Mathematics and Computation. 490, (2025), 129198. https://doi.org/10.1016/j.amc.2024.129198