Independent mutual-visibility sets and distance edge-critical graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912929531559936 |
|---|---|
| author | Tian, Jing Bujtás, Csilla Klavžar, Sandi |
| author_facet | Tian, Jing Bujtás, Csilla Klavžar, Sandi |
| contents | In this paper, connections between independent sets and the variety of mutual-visibility sets are studied. It is proved that every outer mutual-visibility set of a graph is independent if and only if the graph is distance edge-critical. Several constructions yielding distance edge-critical graphs are given. Graphs in which every independent set is a total mutual-visibility or a dual mutual-visibility set are characterized, as well as graphs in which every total mutual-visibility set is independent. Along the way the total mutual-visibility number of some graphs derived from fullerenes is determined. Graphs in which every independent set is a mutual-visibility set are discussed and characterized over diameter four graphs. It is proved that determining the maximum cardinality of an independent mutual-visibility set and deciding whether it equals the independence number of a graph are NP-hard problems, and the same is true for independent total, outer and dual mutual-visibility sets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_23403 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Independent mutual-visibility sets and distance edge-critical graphs Tian, Jing Bujtás, Csilla Klavžar, Sandi Combinatorics In this paper, connections between independent sets and the variety of mutual-visibility sets are studied. It is proved that every outer mutual-visibility set of a graph is independent if and only if the graph is distance edge-critical. Several constructions yielding distance edge-critical graphs are given. Graphs in which every independent set is a total mutual-visibility or a dual mutual-visibility set are characterized, as well as graphs in which every total mutual-visibility set is independent. Along the way the total mutual-visibility number of some graphs derived from fullerenes is determined. Graphs in which every independent set is a mutual-visibility set are discussed and characterized over diameter four graphs. It is proved that determining the maximum cardinality of an independent mutual-visibility set and deciding whether it equals the independence number of a graph are NP-hard problems, and the same is true for independent total, outer and dual mutual-visibility sets. |
| title | Independent mutual-visibility sets and distance edge-critical graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2602.23403 |