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

距離相互可視性着色：(全)支配、正確距離グラフおよびグラフ積との関係

基本情報

  • 論文ID: 2510.10284
  • タイトル: Distance mutual-visibility coloring: relations with (total) domination, exact distance graphs and graph products
  • 著者: Saneesh Babu, Boštjan Brešar, Aparna Lakshmanan S, Babak Samadi
  • 分類: math.CO（組合数学）
  • 発表日: 2025年10月11日
  • 論文リンク: https://arxiv.org/abs/2510.10284

要約

本論文はk-距離相互可視性着色問題を研究している。これはDi Stefanoが2022年に導入した相互可視性概念の拡張である。グラフGの頂点部分集合Sに対して、Sの任意の2つの頂点間に長さ最大k以下の測地線が存在し、その内部頂点がSに含まれない場合、Sをk-距離相互可視性集合（k-DMV集合）と呼ぶ。本論文はこの概念を相互可視性着色と組み合わせ、k-DMV着色数χ_μ_k(G)を定義している。k=2の場合に最も興味深い結果が得られ、χ_μ_2(G) ≤ |V(G)|/2を証明し、支配数、全支配数、および正確距離グラフとの深い関連性を確立している。

研究背景と動機

  1. 問題の起源: 相互可視性概念は元々Di Stefanoが2022年に提案したもので、古典的な「3点非共線性」問題と平面移動ロボットの再配置問題に関連している。
  2. 研究動機:
    • 相互可視性概念は新しいながらも広く注目されている（MathSciNetで20件以上の引用）
    • 既存研究は主に相互可視性集合の最大基数に焦点を当てており、着色問題の体系的研究が不足している
    • k-距離制限により通信がより効率的になり、実用的価値がある
  3. 実用的意義: コンピュータネットワークやソーシャルネットワークにおいて、相互可視性特性を持つ頂点は効率的で秘密の通信を必要とするエンティティを表し、メッセージが他のエンティティを経由しないことを保証する。

核心的貢献

  1. 新概念の導入: k-距離相互可視性着色数χ_μ_k(G)を初めて定義し、クリーク被覆数（k=1）と相互可視性着色数（k≥diam(G)）を統一した。
  2. 基本的な界の確立:
    • χ_μ_2(G) ≤ ⌈|V(G)|/2⌉を証明し、この界を達成するグラフ族を示した
    • 孤立点のないグラフに対して、χ_μ_2(G) ≤ γ_t(G)
    • 周長が最低7以上のグラフに対して、χ_μ_2(G) ≥ γ(G)
  3. 正確距離グラフとの関連性の発見: 孤立点がなく周長が最低7以上のグラフGに対して、θ(G♮2) = γ_t(G)を証明した。
  4. グラフ積の体系的研究:
    • 辞書式積: χ_μ_2(G∘H) ≤ θ(G♮2) ≤ θ((G∘H)♮2)
    • 強積: χ_μ_k(G⊠H) ≤ χ_μ_k(G)χ_μ_k(H)
    • デカルト積: χ_μ_2(G□H) ≥ max{χ_μ_2(G)ρ_2(H), χ_μ_2(H)ρ_2(G)}
  5. 特殊グラフ類の特性化: χ_μ_k(G) = χ_μ(G)（ただしk = diam(G)-1）を満たすブロックグラフを完全に特性化した。

方法の詳細

問題定義

グラフGと正整数kが与えられたとき、k-距離相互可視性着色はV(G)を複数のk-DMV集合に分割する着色スキームである。k-DMV集合Mは以下を満たす：Mの任意の2つの頂点u,vに対して、長さ最大k以下のu,v-測地線が存在し、その内部頂点がMに含まれない。

入力: グラフG = (V,E)、正整数k 出力: V(G)の分割{S_1, S_2, ..., S_t}で、各S_iがk-DMV集合 目標: 分割の集合個数tを最小化する

核心的技術方法

1. 基礎理論の構築

観察1: 直径dのグラフGに対して、単調性チェーンが成立する： χ_μ(G) = χ_μ_d(G) ≤ χ_μ_(G) ≤ ... ≤ χ_μ_1(G) = θ(G)

観察2: 基本的な下界 χ_μ_k(G) ≥ ⌈|V(G)|/μ_k(G)⌉

2. k=2の場合の深い分析

定理4: 任意の連結グラフGに対して、χ_μ_2(G) ≤ ⌈n/2⌉

証明の思路: 生成木に対する帰納法構成により、木を2色で着色可能な構造に分解する。

定理5: Gが孤立点を持たない場合、χ_μ_2(G) ≤ γ_t(G)

証明方法: 構成的証明。全支配集合D = {v_1,...,v_γ_t(G)}を利用し、D_i = N_G(v_i)\⋃_^{i-1}N_G(v_j)と定義して、各D_iが2DMV集合であることを証明する。

3. 周長と支配数の関係

補題6: g(G) ≥ 7の場合、χ_μ_2(G)-着色の各色クラスCは何らかの頂点の閉近傍の部分集合である。

定理7: g(G) ≥ 7の場合、χ_μ_2(G) ≥ γ(G)

技術的革新点

  1. 統一的枠組み: クリーク被覆と相互可視性着色をk-DMV着色の枠組みに統一した
  2. 周長条件の正確な特性化: 周長7がχ_μ_2(G) ≥ γ(G)を保証する最小値であることを証明した
  3. 正確距離グラフとの関連性: 2DMV着色と正確距離-2グラフの深い関連性を初めて確立した
  4. グラフ積の体系的分析: 3つの主要なグラフ積に対して厳密な上下界を提供した

実験設定

理論検証方法

本論文は主に理論的証明方法を採用し、具体的なグラフ族の構成により界の厳密性を検証している：

  1. パスと圏: P_nとC_nの正確なχ_μ_k値を計算した
  2. 特殊グラフ族: 様々な界を達成するグラフ族を構成した
  3. 積グラフ: P_n⊠K_mなどの具体的な積グラフの性質を分析した

主要な例の分析

命題2:

  • パスP_nに対して: χ_μ_k(P_n) = ⌈n/2⌉
  • 圏C_nに対して: χ_μ_k(C_n) = ⌈n/3⌉（n ≤ 3kの場合）、⌈n/2⌉（その他の場合）

命題12: P_n⊠K_m（n≥4, m≥2, k∈{2,...,n-2}）に対して： χ_μ_k(P_n⊠K_m) = 2⌊n/(k+2)⌋ + correction_term

実験結果

主要な理論結果

  1. 基本的な界の厳密性:
    • χ_μ_2(G) ≤ ⌈|V(G)|/2⌉はすべてのグラフで成立し、パスや長い圏により達成される
    • χ_μ_2(G) ≤ γ_t(G)は孤立点のないグラフで成立し、差が任意に大きいグラフ族を構成可能
  2. 周長条件の最適性:
    • 周長が6だがγ(G) = 5 > χ_μ_2(G) = 3の反例を構成した
    • 周長7がχ_μ_2(G) ≥ γ(G)を保証する最小条件であることを証明した
  3. グラフ積結果の鋭さ:
    • 強積の界χ_μ_k(G⊠H) ≤ χ_μ_k(G)χ_μ_k(H)は無限グラフ族により達成される
    • デカルト積の下界はトーラスグラフなどにより達成される

正確距離グラフの驚くべき関連性

定理8: Gが孤立点を持たず、g(G) ≥ 7の場合、θ(G♮2) = χ_i_μ_2(G) = γ_t(G)

この結果は、一見無関係に見える3つのグラフパラメータ間の等式関係を確立し、重要な理論的意義を持つ。

ハイパーキューブの特殊性

命題16: n-ハイパーキューブQ_nに対して、χ_μ_2(Q_n) ≤ γ(Q_n)

予想: すべてのnに対してχ_μ_2(Q_n) = γ(Q_n)が成立する

関連研究

  1. 相互可視性研究: Di Stefano（2022）が基本概念を導入、Ceraら（2025）がk-距離版に拡張
  2. 相互可視性着色: Klavžarら（2025）が初めて相互可視性着色問題を研究
  3. 正確距離グラフ: 1980年代に導入、近年再び注目を集めている
  4. 支配理論: 古典的グラフ論研究分野で、本論文が新たな関連性を確立した

結論と考察

主要な結論

  1. k-距離相互可視性着色はグラフの構造的性質を研究するための新しい視点を提供する
  2. k=2の場合は支配理論と正確距離グラフとの深い関連性を示している
  3. 異なるグラフ積下での振る舞いはこのパラメータの本質的特性を明らかにする
  4. 周長条件はパラメータの界を決定する上で重要な役割を果たす

限界

  1. 主要な結果はk=2の場合に集中しており、一般的なk値の研究が少ない
  2. 某些界の厳密性は特定のグラフ族でのみ検証されている
  3. 計算複雑性の問題には触れられていない

今後の方向

論文は3つの具体的な未解決問題を提示している：

問題1: χ_μ_2(G) = θ(G)を満たすブロックグラフGを特性化せよ

問題2: 連結グラフG,Hに対して、χ_μ_2(G□H) ≥ max{χ_μ_2(G)γ(H), χ_μ_2(H)γ(G)}が成立するか？

問題3: すべてのハイパーキューブに対してχ_μ_2(Q_n) = γ(Q_n)が成立するか？

深い評価

利点

  1. 理論的深さ: グラフ論の複数の分野間に新たな関連性を確立し、特に支配理論と正確距離グラフとの関係が顕著である
  2. 結果の完全性: 多くの厳密な上下界を提供し、界を達成するグラフ族を構成した
  3. 技術的革新: 周長条件の正確な特性化とグラフ積の体系的分析は高度な技巧を示している
  4. 記述の明確性: 定義が明確で、証明が厳密で、構造が合理的である

不足点

  1. 計算複雑性の欠落: χ_μ_k(G)の計算複雑性について論じられていない
  2. 応用の限定: ネットワーク通信応用に言及しているが、具体的な応用シナリオの分析が不足している
  3. アルゴリズム設計: χ_μ_k(G)を計算または近似する効率的なアルゴリズムが欠けている

影響力

  1. 理論的貢献: グラフ論研究に新たな方向を開き、後続研究を促進することが予想される
  2. 技術的価値: 証明技巧と構成方法は関連研究に参考価値がある
  3. 分野横断的可能性: 支配理論との関連性は両分野の交差発展を促進する可能性がある

適用場面

  1. ネットワーク設計: 通信経路の秘密性を保証する必要があるネットワークでの応用
  2. グラフ論研究: グラフの構造的性質を研究するための新しいツール
  3. 組合せ最適化: 関連する最適化問題に理論的基礎を提供

参考文献

論文は18篇の関連文献を引用しており、主に以下を含む：

  • Di Stefano（2022）: 相互可視性概念の原始文献
  • Ceraら: k-距離相互可視性の拡張
  • Klavžarら: 相互可視性着色の初期研究
  • 古典的グラフ論教科書と支配理論文献

総合評価: これは相互可視性という新興研究方向において重要な貢献をした高品質の理論グラフ論論文である。本論文は完全な理論的枠組みを構築しただけでなく、古典的グラフ論概念との深い関連性を発見し、この分野の発展に堅実な基礎を築いている。応用とアルゴリズムの側面ではさらなる研究の余地があるが、その理論的価値と革新性により、この分野の重要な文献となっている。