Connected Mutual-Visibility in Graphs
Abstract
A set S of vertices of a graph G is a connected mutual-visibility set if every two vertices of S are joined by a shortest path whose internal vertices lie outside S, and the subgraph induced by S is connected. We introduce the connected mutual-visibility number μc(G), defined as the maximum cardinality of such a set, and investigate its structural and algorithmic properties. We establish fundamental bounds, derive Nordhaus--Gaddum type inequalities, and characterise the graphs attaining the minimum and maximum possible values. For regular (d,2,−δ)-graphs, we derive general bounds on μc(G) and determine its exact value for the two cubic graphs of defect $2$. We further show that μc(G) is determined locally by the block structure of G, namely, it is equal to the maximum of the corresponding values over the blocks of G. Finally, we present a polynomial-time algorithm for recognising connected mutual-visibility sets and prove that the associated decision problem is NP-complete, even for connected bipartite graphs of diameter at most $4$.
Related
- Diameter-two graphs whose mutual-visibility chromatic number equals their chromatic number
- A variety of the mutual-visibility coloring problem for graphs
- Reconfiguration graphs of mutual-visibility sets
- Mutual-visibility colouring with two colours is NP-complete for every fixed diameter
- Contractable 2-connected subgraphs in minimally 3-connected graphs
BibTeX
@misc{k2026connected,
title = {{Connected Mutual-Visibility in Graphs}},
author = {Tonny K B and Shikhi M},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.18877},
eprint = {2609.18877},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.18877},
}
RIS
TY - UNPB
TI - Connected Mutual-Visibility in Graphs
AU - Tonny K B
AU - Shikhi M
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2609.18877
UR - https://arxiv.org/abs/2609.18877
AB - A set S of vertices of a graph G is a connected mutual-visibility set if every two vertices of S are joined by a shortest path whose internal vertices lie outside S, and the subgraph induced by S is connected. We introduce the connected mutual-visibility number μ_c(G), defined as the maximum cardinality of such a set, and investigate its structural and algorithmic properties. We establish fundamental bounds, derive Nordhaus--Gaddum type inequalities, and characterise the graphs attaining the minimum and maximum possible values. For regular (d,2,−δ)-graphs, we derive general bounds on μ_c(G) and determine its exact value for the two cubic graphs of defect $2$. We further show that μ_c(G) is determined locally by the block structure of G, namely, it is equal to the maximum of the corresponding values over the blocks of G. Finally, we present a polynomial-time algorithm for recognising connected mutual-visibility sets and prove that the associated decision problem is NP-complete, even for connected bipartite graphs of diameter at most $4$.
ER -