平面弦圏から生じる回転対称平面グラフの局所分数計量次元

基本情報

• 論文ID: 2105.07808
• タイトル: Local fractional metric dimension of rotationally symmetric planar graphs arisen from planar chorded cycles
• 著者: Shahbaz Ali, Raúl M. Falcón, Muhammad Khalid Mahmood
• 分類: math.CO (組合数学)
• 発表日: 2021年5月17日 (arXiv プレプリント)
• 論文リンク: https://arxiv.org/abs/2105.07808

要約

本論文は、平面弦圏に基づく辺マージ構成から生じる回転対称平面グラフの新しい族を記述している。位数が6以下の弦圏から生じるグラフについて、それらの局所分数計量次元を確立した。漸近挙動の分析を通じて、定数または有界の局所分数次元を持つ回転対称平面グラフの新しい族の存在性を保証した。

研究背景と動機

問題背景

1. 計量次元問題の起源: 1970年代にSlaterおよびHarary & Melterにより独立に導入され、グラフ内で距離ベクトルにより一意に表現できる頂点の最小数を決定することを目的とする
2. 問題の複雑性: 計量次元問題はNP困難であるが、異なるタイプのグラフに対して明示的な解が得られている
3. 実用的価値: ロボット航法、パターン認識、画像処理、化学化合物表現、組合せ最適化およびネットワークなどの分野で重要な応用を持つ

研究動機

1. 理論的必要性: Imranら学者により、定数計量次元を持つ(回転対称)平面グラフ族を特性化する問題が提起された
2. 技術的発展: 2000年にChartrandらが計量次元問題を整数計画問題として定式化し、その後CurrieとOellermannが線形計画緩和を提案して分数計量次元の概念を導入した
3. 局所化研究: 2018年にBenishらが隣接頂点のみを関連させる局所分数計量次元の概念を導入し、この研究分野はまだ初期段階にある

既存手法の限界

1. 局所分数計量次元の研究は非常に限定的であり、少数のグラフタイプにのみ明示的な結果がある
2. Liuらの最近の研究には技術的誤りがあり、全面的な再分析が必要である
3. 高位数弦圏構成グラフの体系的研究が不足している

核心的貢献

1. 新しいグラフ族の構成: 平面弦圏の辺マージに基づく回転対称平面グラフの新しい族$G_m(G)$を記述した
2. 次元計算: 位数$n ≤ 6$の平面弦圏から生じるすべての回転対称平面グラフの局所分数計量次元を確立した
3. 漸近分析: これらのグラフ族の局所分数計量次元の漸近挙動分析を提供した
4. 理論的修正: 文献における車輪グラフの局所分数計量次元に関する誤った結果を修正した
5. 分類の完全性: 四角形、五角形および六角形弦圏のすべての非同型ケースについて包括的な分析を実施した

方法の詳細

タスク定義

位数$n$の平面弦圏$G$から生じる回転対称平面グラフ$G_m(G)$の局所分数計量次元を研究する。ここで$m ≥ 2$はコピー数である。

グラフ構成方法

平面弦圏$G$の$m$個の互いに素なコピー$G_1, G_2, ..., G_m$が与えられたとき、以下の連続的な辺マージにより$G_m(G)$を構成する：

1. $G_1(G) := G_1 \cdot G_2(v_2^1v_3^1, v_{n-1}^2v_n^2 : v_{n-1}^2v_n^2)$
2. $G_k(G) := G_{k-1}(G) \cdot G_{k+1}(v_2^kv_3^k, v_{n-1}^{k+1}v_n^{k+1} : v_{n-1}^{k+1}v_n^{k+1})$、$k \in \{2,...,m-1\}$の場合
3. $G_m(G) := G_{m-1}(G) \cdot G_m(v_2^mv_3^m, v_{n-1}^1v_n^1 : v_{n-1}^1v_n^1)$

結果のグラフ$G_m(G)$は位数$m \cdot (n-2)$の回転対称平面グラフである。

核心概念の定義

局所分数計量次元

グラフ$G$に対して、局所分数計量次元は以下のように定義される： $\text{ldim}_f(G) := \min\left\{\sum_{v \in V(G)} \vartheta(v) : \vartheta \text{は} G \text{の局所解析関数}\right\}$

ここで局所解析関数$\vartheta: V(G) \to [0,1]$は以下を満たす： $\sum_{u \in R\{v,w\}} \vartheta(u) \geq 1$ すべての隣接頂点対$vw \in E(G)$に対して成立する。

主要補題

補題2.1: 位数$n ≥ 2$の有限連結グラフ$G$に対して：

• $\text{ldim}_f(G) \leq \text{dim}_f(G)$
• $\frac{n}{n - \text{ldim}(G) + 1} \leq \text{ldim}_f(G) \leq \frac{n}{\ell(G)} \leq \frac{n}{2}$
• $\text{ldim}_f(G) = 1$ 当且つ当に $G$が二部グラフ
• $\text{ldim}_f(G) = \frac{n}{2}$ 当且つ当に $V(G)$の各頂点が真の双子頂点を持つ

技術的革新点

1. 体系的分析: 位数が6以下のすべての平面弦圏から構成される回転対称グラフの完全な分析を初めて実施した
2. 計算方法: 線形計画法により局所分数計量次元の精確な値または上界を求解した
3. 漸近分析: 各グラフ族の局所分数計量次元の漸近挙動パターンを確立した
4. 誤り修正: 文献2における車輪グラフの局所分数計量次元に関する誤った結果を修正した

実験設定

グラフクラスの分析

論文は以下のグラフクラスを分析した：

• 四角形弦圏: Q₁, Q₂ (2種類)
• 五角形弦圏: P₁ から P₆ (6種類)
• 六角形弦圏: H₁ から H₁₇ (17種類)

計算方法

1. 線形計画法: 各グラフクラスに対して対応する線形計画問題を構成した
2. 対称性の利用: グラフの回転対称性を利用して計算を簡略化した
3. 解析近傍分析: 重要な辺対の解析近傍サイズ$|R\{v,w\}|$を計算した

評価指標

• 局所分数計量次元の精確な値
• 漸近上界
• 理論的下界との比較

実験結果

主要結果

四角形の場合

命題3.1: $m ≥ 2$に対して：

• $\text{ldim}_f(G_m(Q_1)) = \begin{cases} \frac{3}{2}, & \text{if } m = 2 \\ \frac{m}{2}, & \text{otherwise} \end{cases}$
• $\text{ldim}_f(G_m(Q_2)) = \begin{cases} \frac{3}{2}, & \text{if } m \leq 4 \\ \frac{m}{4}, & \text{otherwise} \end{cases}$

五角形の場合

定理4.1: すべての五角形弦圏$P_1$から$P_6$から構成されるグラフの局所分数計量次元上界を確立した。例えば：

• $\text{ldim}_f(G_m(P_2)) \leq \begin{cases} \frac{2m}{m+1}, & \text{if } m \text{ is odd} \\ \frac{6m}{3m+2}, & \text{otherwise} \end{cases}$

六角形の場合

定理4.2: 六角形弦圏$H_1$から$H_{17}$に対して：

• $\text{ldim}_f(G_m(H_1)) = \text{ldim}_f(G_m(H_2)) = 1$ (二部グラフ)
• その他の場合は対応する上界公式を与えた

車輪グラフの修正結果

補題3.1: 位数$n ≥ 4$の車輪グラフ$W_n$に対して：