Independent mutual-visibility sets and distance edge-critical graphs

Jing Tian, Csilla Bujtás, Sandi Klavžar · 2026

Read Independent mutual-visibility sets and distance edge-critical graphs by Jing Tian, Csilla Bujtás, Sandi Klavžar (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-23403.txt.

Description

Jing Tian and two co-authors explore links between independent sets and mutual-visibility sets in graphs. In a mutual-visibility set, any two members can 'see' each other along a shortest path that avoids other members. Every outer mutual-visibility set of a graph is independent if and only if the graph is distance edge-critical.

The paper gives several constructions of distance edge-critical graphs. It characterizes graphs where every independent set is a total or dual mutual-visibility set, and where every total one is independent. It also pins down the total mutual-visibility number of some fullerene-derived graphs and treats diameter-four graphs where every independent set is a mutual-visibility set. Finally, it proves NP-hardness for finding the largest independent mutual-visibility set and for deciding whether it equals the independence number, with the same hardness for the total, outer, and dual cases.

Catalog record

CREATORJing Tian, Csilla Bujtás, Sandi Klavžar
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE42 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-23403

Browse the full library · About the Tower of Babel