Skip to content
Preprint

Connected Mutual-Visibility in Graphs

Sep 2026 · 0 citations · 20 references
Mathematics

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 $\mu_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,-\delta)$-graphs, we derive general bounds on $\mu_c(G)$ and determine its exact value for the two cubic graphs of defect $2$. We further show that $\mu_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$.

View source

Similar papers

Preprint Sep 2026

Connected graphs with minimum adjacency spectral gap

Let $G$ be a connected graph, and let $\lambda_1(G)>\lambda_2(G)$ denote its two largest adjacency eigenvalues. The spectral gap of $G$ is defined as the difference $\lambda_1(G) - \lambda_2(G)$. For integers $r\geq 2$ and $s\geq 0$, the double kite $DK(r,s)$ is formed by taking two vertex-disjoint copies of the comple...

Le-Le Liu, Michael Tait, Yi Wang · 1 citation
Preprint Aug 2026

The Cayley Completion of a Graph

A finite connected graph is rarely a Cayley graph. We measure how far it is from being one: given $G$ with $n$ vertices and $m$ edges, how few edges must be added, or added and deleted, before the result is a Cayley graph of an abelian group of order $n$ on the same vertex set? This defines two invariants, the completi...

Rigobert Fokam Souop, Laurent Bitjoka · 2 citations · ⚡2
Open access Aug 2026

OUTER-CONNECTED WEAKLY CONNECTED 2 DOMINATION IN GRAPHS

Let $G = (V(G), E(G))$ be a nontrivial connected graph. A subset $S\subseteq V(G)$ is called an outer-connected weakly connected 2-dominating set in $G$ if every vertex $v \in V(G)\setminus S$ is adjacent to at least two vertices in $S$, the subgraph $\langle S \rangle_w$ weakly induced by $S$ is connected, and the ind...

Kient Rey L. Zuyco, Mae P. Militante, D. J. Tejada et al. · 0 citations
Preprint Oct 2026

Graph Sensitivity of Cartesian Products with Matched Bridges

For a graph $G$, let $f_t(G)$ denote the minimum of the maximum degree of an induced subgraph with $\alpha(G)+t$ vertices, where $\alpha(G)$ is the independence number, and write $f(G)=f_1(G)$. Huang's theorem gives $f(Q_k)\ge\lceil\sqrt{k}\rceil$ for the $k$-dimensional hypercube $Q_k$. We extend this lower bound to C...

Zhen-Mu Hong, Zi-Yi Wu, Zheng-Jiang Xia · 0 citations
Preprint Sep 2026

The Maximum Mutual Visibility Set on a Cactus Graph and the Self-stabilizing Constructions

Given a graph $G=(V,E)$, let $S$ ($\subseteq V$) be a set of vertices. Two vertices are \emph{mutually visible} if there exists a shortest path in $G$ between them that does not contain any other vertex of $S$. A set $S$ is a \emph{Mutual Visibility Set} (\MVS) if every pair of vertices in $S$ is mutually visible. The...

Yonghwan Kim, Y. Sudo · 0 citations
#edge computing Preprint Sep 2026

Computing and Bounding the Number of Eulerian Orientations for Certain Classes of $4$-Regular Graphs

The bounds on the number of Eulerian orientations for certain classes of connected, loopless $4-regular graphs are improved and a divide-and-conquer algorithm is provided that leverages structural properties to compute the exact number of Eulerian orientations for separable graphs without exhaustive enumeration.

Evangelos Bartzos, Michalis Samaris · 1 citation

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.