Local fractional metric dimension of rotationally symmetric planar graphs arisen from planar chorded cycles

基本信息

• 论文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. 分类完整性: 对四边形、五边形和六边形弦圈的所有非同构情况进行了全面分析

方法详解

任务定义

研究旋转对称平面图$G_m(G)$的局部分数度量维数，其中$G$是阶数为$n$的平面弦圈，$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$：