2025-11-18T04:55:13.602783

Metric Dimension of Generalized Theta Graphs

Benakli, Froitzheim, Martinez

A vertex $w$ in a graph $G$ is said to resolve two vertices $u$ and $v$ if $d(w,u)\neq d(w, v)$. A set $W$ of vertices is a resolving set for $G$ if every pair of distinct vertices is resolved by some vertex in $W$. The metric dimension of $G$ is the minimum cardinality of such a set. In this paper, we investigate the metric dimension of generalized theta graphs, providing exact values and structural insights for several subclasses.

academic

Metric Dimension of Generalized Theta Graphs

基本信息

论文ID: 2510.12100
标题: Metric Dimension of Generalized Theta Graphs
作者: Nadia Benakli, Nicole Froitzheim, David Martinez
分类: math.CO (组合数学)
发表时间: 2025年10月14日 (arXiv预印本)
论文链接: https://arxiv.org/abs/2510.12100

摘要

本文研究广义theta图的度量维数问题。对于图G中的顶点w，如果d(w,u)≠d(w,v)，则称w能够区分顶点u和v。如果顶点集合W能够区分图中每一对不同的顶点，则W称为解析集。图G的度量维数是最小解析集的基数。本文深入研究了广义theta图的度量维数，为多个子类提供了精确值和结构性洞察。

研究背景与动机

核心问题: 度量维数是图论中的重要不变量，用于基于顶点到固定顶点子集的距离来区分图中的顶点。本文专门研究广义theta图这一特殊图类的度量维数。
实际意义: 度量维数在多个学科领域有实际应用，包括：
- 机器人导航
- 网络定位
- 化学结构识别
现有研究局限:
- 循环图的度量维数已知为2
- 单环图的度量维数已被确定
- 双环图分为三类，其中theta图(Type 3)的度量维数已有部分结果
- 但广义theta图(多于3条路径)的度量维数研究不够充分
研究动机: 广义theta图是循环图的自然扩展，由两个顶点通过多条内部不相交的路径连接。理解其度量维数对图论理论发展和实际应用都具有重要意义。

核心贡献

建立了广义theta图度量维数的一般界限：对于Θ(s₁,s₂,...,sₘ)，证明了m-3 ≤ β(G) ≤ m
提出并证明了同构路径定理(Identical Paths Theorem)：为具有相同长度内部不相交路径的图类提供了度量维数下界
给出了多个重要子类的精确度量维数：
- 均匀广义theta图Θ(sᵐ)
- 连续广义theta图(路径长度连续)
- 特殊配置的广义theta图
提供了theta图(m=3)度量维数的新证明：重新证明了已知结果β(Θ(s₁,s₂,s₃)) = 3当且仅当所有sᵢ相等或s₁=s₂且s₃=s₁+2
完整分析了4重广义theta图：系统研究了m=4情况下的所有可能配置

方法详解

任务定义

给定广义theta图Θ(s₁,s₂,...,sₘ)，其中：

两个中心顶点c₁和c₂
m条内部不相交路径Pᵢ，长度为sᵢ+1
假设s₁ ≤ s₂ ≤ ... ≤ sₘ

目标：确定该图的度量维数β(G)，即最小解析集的大小。

核心理论框架

1. 同构路径定理(Identical Paths Theorem)

定理3.3: 设图G满足|IP(G)| = n，其中IP(G)是同构路径集合，则： $\beta(G) \geq \sum_{i=1}^n (m_i - 1)$

这个定理的关键思想是：如果图中存在多条相同长度的内部不相交路径连接同一对顶点，则必须在至少m-1条路径上各选择一个内部顶点作为解析顶点。

2. 互相最远距离概念

对于顶点u和v，如果u MD v且v MD u，则记为u MMD v。这个概念用于分析哪些顶点对难以区分。

3. 路径解析策略

命题3.8: 如果M₁ ≠ M₂，则W = {w₁,w₂}能够解析路径P，其中Mᵢ是与wᵢ互相最远距离的顶点集合。

技术创新点

分层分析方法: 将广义theta图的解析问题分解为：
- 路径内部顶点的解析
- 不同路径间顶点的解析
- 中心顶点的特殊处理
几何对称性利用: 利用广义theta图的对称性质，通过选择合适位置的解析顶点来打破对称性
奇偶性分析: 系统利用路径长度的奇偶性来确定最优解析集的构造

主要结果

一般界限

定理1.2: 对于广义theta图Θ(s₁,s₂,...,sₘ)，其中m ≥ 2： $m-3 \leq \beta(\Theta(s_1,s_2,...,s_m)) \leq m$

均匀情况

定理3.17-3.19: 对于均匀广义theta图Θ(sᵐ)：

$\beta(\Theta(s^m)) = \begin{cases} m-1 & \text{如果 } m \geq 5 \text{ 且 } s \geq 2 \\ m-1 & \text{如果 } m = 4 \text{ 且 } s > 2 \\ m & \text{其他情况} \end{cases}$

Theta图(m=3)

定理4.4: $\beta(\Theta(s_1,s_2,s_3)) = \begin{cases} 3 & \text{如果 } s_1=s_2=s_3 \text{ 或 } s_1=s_2 \text{ 且 } s_3=s_1+2 \\ 2 & \text{其他情况} \end{cases}$

4重广义theta图

定理5.12: 对于Θ(s₁,s₂,s₃,s₄)：

$\beta(\Theta(s_1,s_2,s_3,s_4)) = \begin{cases} 4 & \text{对于 } \Theta(1^4), \Theta(1^3,3), \Theta(2^4), \Theta(2^3,4) \\ 2 & \text{如果 } s_2=s_1+1, s_2=s_3 \text{ 且 } s_4 \geq s_1+4 \\ 2 & \text{如果 } s_2=s_1+1 \text{ 且 } s_2 < s_3 \leq s_4 \\ 3 & \text{其余情况} \end{cases}$