Graphs with a unique maximum independent set up to automorphisms

• Published in: Discrete Applied Mathematics 2022-08, Vol.317, p.124-135
• Main Authors: Brešar, Boštjan, Dravec, Tanja, Gorzkowska, Aleksandra, Kleszcz, Elżbieta
• Format: Article
• Language: English
• Subjects: Algorithms; Apexes; Automorphisms; Cartesian coordinates; Cartesian product; Chordal graph; Deletion; Graph automorphism; Graph theory; Graphs; Maximum independent set; Polynomials; Tree; Trees (mathematics)
• ISSN: 0166-218X; 1872-6771
• DOI: 10.1016/j.dam.2022.04.003

If for every two maximum independent sets A and B in a graph G there exists an automorphism of G that maps A to B, then we call G an α-iso-unique graph. We extend several known characterizations of trees that have a unique maximum independent set obtaining characterizations of α-iso-unique trees. Such trees either have the property that the deletion of any edge does not affect the independence number, or they have the central edge, which connects two isomorphic subtrees, and only the deletion of the central edge increases the independence number. One of the characterizations results in a linear time algorithm to recognize whether a given tree is α-iso-unique. In contrast, we prove that the problem of recognizing whether an arbitrary graph is α-iso-unique is not polynomial unless P = NP. Constructions of large families of α-iso-unique graphs are given involving simplicial vertices and chordal graphs. In particular, we show that every graph is an induced subgraph of an α-iso-unique graph. Finally, α-iso-unique graphs are characterized among Cartesian products G□H of co-prime graphs G and H such that α(G□H)=α(H)|V(G)|.