首页|Graphs with a unique maximum independent set up to automorphisms
Graphs with a unique maximum independent set up to automorphisms
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
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 alpha-iso-unique graph. We extend several known characterizations of trees that have a unique maximum independent set obtaining characterizations of alpha-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 alpha-iso-unique. In contrast, we prove that the problem of recognizing whether an arbitrary graph is alpha-iso-unique is not polynomial unless P = NP. Constructions of large families of alpha-iso-unique graphs are given involving simplicial vertices and chordal graphs. In particular, we show that every graph is an induced subgraph of an alpha-iso-unique graph. Finally, alpha-iso-unique graphs are characterized among Cartesian products G rectangle H of co-prime graphs G and H such that alpha(G rectangle H) = alpha(H)vertical bar V(G)vertical bar. (C) 2022 Elsevier B.V. All rights reserved.
Maximum independent setCartesian productGraph automorphismChordal graphTree
NSTL
Elsevier
