2025-11-17T18:31:12.470972

Distance mutual-visibility coloring: relations with (total) domination, exact distance graphs and graph products

Babu, Brešar, S et al.
The concept of mutual-visibility (MV) has been extended in several directions. A vertex subset $S$ of a graph $G$ is a $k$-distance mutual-visibility ($k$DMV) set if for any two vertices in $S$, there is a geodesic between them of length at most $k$ whose internal vertices are not in $S$. In this paper, we combine this with the MV coloring as follows. For any integer $k\geq1$, a $k$DMV coloring of $G$ is a partition of $V(G)$ into $k$DMV sets, and the $k$DMV chromatic number $χ_{μ_k}(G)$ is the minimum cardinality of such a partition. When $k=1$ or $k\ge {\rm diam}(G)$, it equals the clique cover number $θ(G)$ or the MV chromatic number $χ_μ(G)$, respectively. So, our attention is given to $1<k<{\rm diam}(G)$ with $k=2$ producing the most interesting results. We prove that $χ_{μ_2}(G)\le|V(G)|/2$ and present large families of graphs that attain the bound. In addition, $χ_{μ_2}(G)$ is bounded from above by the total domination number $γ_t(G)$ if $G$ is isolate-free, while in graphs $G$ with girth $g(G)\geq7$, $χ_{μ_2}(G)$ is bounded from below by the domination number $γ(G)$. A surprising relation with the exact distance-2 graphs is found, which results in $θ(G^{[\natural2]})=γ_{t}(G)$ for any isolate-free graph $G$ with $g(G)\geq7$. The relation is explored further in lexicographic product graphs, where we prove the sharp inequalities $χ_{μ_{2}}(G\circ H)\leq θ(G^{[\natural2]})\leq θ\big{(}(G\circ H)^{[\natural2]}\big{)}$. We also prove a sharp lower (resp. upper) bound on $χ_{μ_2}$ (resp. $χ_{μ_k}$) for the Cartesian (resp. strong) product of two connected graphs and show that they are widely sharp. Finally, we characterize the block graphs $G$ with $χ_{μ_k}(G)=χ_μ(G)$, where $k={\rm diam}(G)-1$.
academic

Distance mutual-visibility coloring: relations with (total) domination, exact distance graphs and graph products

Basic Information

  • Paper ID: 2510.10284
  • Title: Distance mutual-visibility coloring: relations with (total) domination, exact distance graphs and graph products
  • Authors: Saneesh Babu, Boštjan Brešar, Aparna Lakshmanan S, Babak Samadi
  • Classification: math.CO (Combinatorics)
  • Publication Date: October 11, 2025
  • Paper Link: https://arxiv.org/abs/2510.10284

Abstract

This paper investigates k-distance mutual-visibility coloring, an extension of the mutual-visibility concept introduced by Di Stefano in 2022. For a vertex subset S of graph G, S is called a k-distance mutual-visibility set (k-DMV set) if any two vertices in S are connected by a geodesic of length at most k whose internal vertices are not in S. The paper combines this concept with mutual-visibility coloring to define the k-DMV chromatic number χ_μ_k(G). The study reveals that the most interesting results occur when k=2, proving that χ_μ_2(G) ≤ |V(G)|/2 and establishing profound connections with domination number, total domination number, and exact distance graphs.

Research Background and Motivation

  1. Problem Origin: The mutual-visibility concept was originally introduced by Di Stefano in 2022, related to the classical "three points non-collinear" problem and planar robot repositioning problems.
  2. Research Motivation:
    • Although novel, the mutual-visibility concept has gained widespread attention (with over 20 citations in MathSciNet)
    • Existing research primarily focuses on the maximum cardinality of mutual-visibility sets, lacking systematic study of coloring problems
    • k-distance restrictions enable more efficient communication with practical application value
  3. Practical Significance: In computer networks or social networks, vertices with mutual-visibility properties can represent entities requiring efficient and confidential communication, ensuring messages are not transmitted through other entities.

Core Contributions

  1. Introduction of New Concept: First defines the k-distance mutual-visibility chromatic number χ_μ_k(G), unifying the clique cover number (k=1) and mutual-visibility chromatic number (k≥diam(G))
  2. Establishment of Fundamental Bounds:
    • Proves χ_μ_2(G) ≤ ⌈|V(G)|/2⌉ and provides graph families achieving this bound
    • For graphs without isolated vertices: χ_μ_2(G) ≤ γ_t(G)
    • For graphs with girth at least 7: χ_μ_2(G) ≥ γ(G)
  3. Discovery of Connections with Exact Distance Graphs: Proves that for graphs G without isolated vertices and girth at least 7, θ(G♮2) = γ_t(G)
  4. Systematic Study of Graph Products:
    • Lexicographic product: χ_μ_2(G∘H) ≤ θ(G♮2) ≤ θ((G∘H)♮2)
    • Strong product: χ_μ_k(G⊠H) ≤ χ_μ_k(G)χ_μ_k(H)
    • Cartesian product: χ_μ_2(G□H) ≥ max{χ_μ_2(G)ρ_2(H), χ_μ_2(H)ρ_2(G)}
  5. Characterization of Special Graph Classes: Completely characterizes block graphs satisfying χ_μ_k(G) = χ_μ(G) where k = diam(G)-1

Methodology Details

Problem Definition

Given a graph G and positive integer k, a k-distance mutual-visibility coloring is a partition of V(G) into several k-DMV sets. A k-DMV set M satisfies: for any two vertices u,v in M, there exists a u,v-geodesic of length at most k whose internal vertices are not in M.

Input: Graph G = (V,E), positive integer k Output: A partition {S_1, S_2, ..., S_t} of V(G) such that each S_i is a k-DMV set Objective: Minimize the number of sets t in the partition

Core Technical Methods

1. Foundational Theory Development

Observation 1: For a graph G with diameter d, there exists a monotonicity chain: χ_μ(G) = χ_μ_d(G) ≤ χ_μ_(G) ≤ ... ≤ χ_μ_1(G) = θ(G)

Observation 2: Basic lower bound χ_μ_k(G) ≥ ⌈|V(G)|/μ_k(G)⌉

2. In-depth Analysis of k=2 Case

Theorem 4: For any connected graph G, χ_μ_2(G) ≤ ⌈n/2⌉

Proof Strategy: Through inductive construction on spanning trees, decomposing the tree into structures colorable with two colors.

Theorem 5: If G has no isolated vertices, then χ_μ_2(G) ≤ γ_t(G)

Proof Method: Constructive proof utilizing total dominating set D = {v_1,...,v_γ_t(G)}, defining D_i = N_G(v_i)\⋃_^{i-1}N_G(v_j), proving each D_i is a 2-DMV set.

3. Relationship Between Girth and Domination Number

Lemma 6: If g(G) ≥ 7, then each color class C in a χ_μ_2(G)-coloring is a subset of some vertex's closed neighborhood.

Theorem 7: If g(G) ≥ 7, then χ_μ_2(G) ≥ γ(G)

Technical Innovations

  1. Unified Framework: Unifies clique cover and mutual-visibility coloring within the k-DMV coloring framework
  2. Precise Characterization of Girth Conditions: Proves that girth 7 is the minimum value guaranteeing χ_μ_2(G) ≥ γ(G)
  3. Exact Distance Graph Connections: First establishes profound connections between 2-DMV coloring and exact distance-2 graphs
  4. Systematic Analysis of Graph Products: Provides tight bounds for three major graph products

Experimental Setup

Theoretical Verification Methods

The paper primarily employs theoretical proof methods, verifying bound tightness through construction of specific graph families:

  1. Paths and Cycles: Computes exact χ_μ_k values for P_n and C_n
  2. Special Graph Families: Constructs graph families achieving various bounds
  3. Product Graphs: Analyzes properties of specific product graphs like P_n⊠K_m

Key Example Analysis

Proposition 2:

  • For path P_n: χ_μ_k(P_n) = ⌈n/2⌉
  • For cycle C_n: χ_μ_k(C_n) = ⌈n/3⌉ (when n ≤ 3k), ⌈n/2⌉ (otherwise)

Proposition 12: For P_n⊠K_m (n≥4, m≥2, k∈{2,...,n-2}): χ_μ_k(P_n⊠K_m) = 2⌊n/(k+2)⌋ + correction_term

Experimental Results

Main Theoretical Results

  1. Tightness of Basic Bounds:
    • χ_μ_2(G) ≤ ⌈|V(G)|/2⌉ holds for all graphs and is achieved by paths, long cycles, etc.
    • χ_μ_2(G) ≤ γ_t(G) holds for graphs without isolated vertices, with constructible graph families where the difference can be arbitrarily large
  2. Optimality of Girth Conditions:
    • Constructs counterexample with girth 6 but γ(G) = 5 > χ_μ_2(G) = 3
    • Proves girth 7 is the minimum condition guaranteeing χ_μ_2(G) ≥ γ(G)
  3. Sharpness of Graph Product Results:
    • Strong product bound χ_μ_k(G⊠H) ≤ χ_μ_k(G)χ_μ_k(H) is achieved by infinite graph families
    • Cartesian product lower bounds are achieved by toroidal graphs, etc.

Surprising Connections with Exact Distance Graphs

Theorem 8: If G has no isolated vertices and g(G) ≥ 7, then θ(G♮2) = χ_i_μ_2(G) = γ_t(G)

This result establishes equality relationships between three seemingly unrelated graph parameters, with significant theoretical importance.

Special Properties of Hypercubes

Proposition 16: For n-dimensional hypercube Q_n, χ_μ_2(Q_n) ≤ γ(Q_n)

Conjecture: χ_μ_2(Q_n) = γ(Q_n) holds for all n

Related Work

  1. Mutual-visibility Research: Di Stefano (2022) introduces basic concepts; Cera et al. extend to k-distance versions
  2. Mutual-visibility Coloring: Klavžar et al. (2025) first study mutual-visibility coloring problems
  3. Exact Distance Graphs: Introduced in the 1980s, recently regaining attention
  4. Domination Theory: Classical graph theory research field, establishing new connections with this paper

Conclusions and Discussion

Main Conclusions

  1. k-distance mutual-visibility coloring provides a new perspective for studying graph structural properties
  2. The k=2 case reveals profound connections with domination theory and exact distance graphs
  3. Behavior under different graph products reveals essential characteristics of this parameter
  4. Girth conditions play a key role in determining parameter bounds

Limitations

  1. Main results concentrate on the k=2 case, with limited research on general k values
  2. Tightness of certain bounds is verified only in specific graph families
  3. Computational complexity issues are not addressed

Future Directions

The paper proposes three specific open problems:

Problem 1: Characterize block graphs G satisfying χ_μ_2(G) = θ(G)

Problem 2: For connected graphs G,H, does χ_μ_2(G□H) ≥ max{χ_μ_2(G)γ(H), χ_μ_2(H)γ(G)} hold?

Problem 3: Does χ_μ_2(Q_n) = γ(Q_n) hold for all hypercubes?

In-depth Evaluation

Strengths

  1. Theoretical Depth: Establishes new connections between multiple graph theory branches, particularly with domination theory and exact distance graphs
  2. Result Completeness: Provides numerous tight bounds and constructs graph families achieving these bounds
  3. Technical Innovation: Precise characterization of girth conditions and systematic analysis of graph products demonstrate sophisticated techniques
  4. Clear Writing: Definitions are precise, proofs are rigorous, and structure is logical

Weaknesses

  1. Missing Computational Complexity: Does not discuss computational complexity of χ_μ_k(G)
  2. Limited Applications: While network communication applications are mentioned, lacks concrete application scenario analysis
  3. Algorithm Design: Lacks efficient algorithms for computing or approximating χ_μ_k(G)

Impact

  1. Theoretical Contribution: Opens new directions for graph theory research, expected to inspire subsequent studies
  2. Technical Value: Proof techniques and construction methods serve as references for related research
  3. Cross-disciplinary Potential: Connections with domination theory may promote interdisciplinary development

Applicable Scenarios

  1. Network Design: Application in networks requiring communication path privacy
  2. Graph Theory Research: As a new tool for studying graph structural properties
  3. Combinatorial Optimization: Provides theoretical foundation for related optimization problems

References

The paper cites 18 related references, primarily including:

  • Di Stefano (2022): Original mutual-visibility concept literature
  • Cera et al.: Extensions to k-distance mutual-visibility
  • Klavžar et al.: First study of mutual-visibility coloring
  • Classical graph theory textbooks and domination theory literature

Overall Assessment: This is a high-quality theoretical graph theory paper making important contributions to the emerging research direction of mutual-visibility. The paper not only establishes a complete theoretical framework but also discovers profound connections with classical graph theory concepts, laying a solid foundation for the field's development. While further research is needed in applications and algorithms, its theoretical value and innovation make it an important reference in the field.