{"ID":23003499,"CreatedAt":"2026-09-17T04:20:54.235930923Z","UpdatedAt":"2026-09-17T04:20:54.235930923Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.18877","arxiv_id":"2609.18877","title":"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 $\\mathsf{NP}$-complete, even for connected bipartite graphs of diameter at most $4$.","short_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...","url_abs":"https://arxiv.org/abs/2609.18877","url_pdf":"https://arxiv.org/pdf/2609.18877v1","authors":"[\"Tonny K B\",\"Shikhi M\"]","published":"2026-09-16T16:12:51Z","proceeding":"math.CO","tasks":"[\"math.CO\"]","methods":"[]","has_code":false}