Szczegóły publikacji
Opis bibliograficzny
Graphs with a unique maximum independent set up to automorphisms / Boštjan Brešar, Tanja Dravec, Aleksandra GORZKOWSKA, Elżbieta KLESZCZ // Discrete Applied Mathematics ; ISSN 0166-218X. — 2022 — vol. 317, s. 124-135. — Bibliogr. s. 134-135, Abstr. — Publikacja dostępna online od: 2022-05-19. — E. Kleszcz - dod. afiliacja: University of Johannesburg, South Africa
Autorzy (4)
- Brešar Boštjan
- Dravec Tanja
- AGHGorzkowska Aleksandra
- AGHKleszcz Elżbieta
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 140210 |
|---|---|
| Data dodania do BaDAP | 2022-05-23 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.dam.2022.04.003 |
| Rok publikacji | 2022 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Discrete Applied Mathematics |
Abstract
If for every two maximum independent sets and in a graph there exists an automorphism of that maps to , then we call 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 of co-prime graphs and such that .
