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

Basic Information

  • Paper ID: 2510.12100
  • Title: Metric Dimension of Generalized Theta Graphs
  • Authors: Nadia Benakli, Nicole Froitzheim, David Martinez
  • Classification: math.CO (Combinatorics)
  • Publication Date: October 14, 2025 (arXiv preprint)
  • Paper Link: https://arxiv.org/abs/2510.12100

Abstract

This paper investigates the metric dimension problem for generalized theta graphs. For a vertex w in graph G, w is said to distinguish vertices u and v if d(w,u) ≠ d(w,v). A vertex set W is called a resolving set if it distinguishes every pair of distinct vertices in the graph. The metric dimension of graph G is the cardinality of a minimum resolving set. This paper provides an in-depth study of the metric dimension of generalized theta graphs, offering exact values and structural insights for multiple subclasses.

Research Background and Motivation

  1. Core Problem: Metric dimension is an important graph invariant used to distinguish vertices in a graph based on their distances to a fixed subset of vertices. This paper specifically studies the metric dimension of generalized theta graphs, a special graph class.
  2. Practical Significance: Metric dimension has practical applications in multiple disciplines, including:
    • Robot navigation
    • Network localization
    • Chemical structure identification
  3. Limitations of Existing Research:
    • The metric dimension of cycles is known to be 2
    • The metric dimension of unicyclic graphs has been determined
    • Bicyclic graphs are classified into three types, with partial results for theta graphs (Type 3)
    • However, the metric dimension of generalized theta graphs (with more than 3 paths) has not been sufficiently studied
  4. Research Motivation: Generalized theta graphs are natural extensions of cycles, formed by connecting two vertices through multiple internally disjoint paths. Understanding their metric dimension is important for both theoretical development and practical applications in graph theory.

Core Contributions

  1. Established general bounds for the metric dimension of generalized theta graphs: For Θ(s₁,s₂,...,sₘ), proved that m-3 ≤ β(G) ≤ m
  2. Proposed and proved the Identical Paths Theorem: Provides a lower bound for the metric dimension of graph classes with internally disjoint paths of equal length
  3. Provided exact metric dimensions for multiple important subclasses:
    • Uniform generalized theta graphs Θ(sᵐ)
    • Consecutive generalized theta graphs (with consecutive path lengths)
    • Generalized theta graphs with special configurations
  4. Provided new proofs for the metric dimension of theta graphs (m=3): Re-proved the known result β(Θ(s₁,s₂,s₃)) = 3 if and only if all sᵢ are equal or s₁=s₂ and s₃=s₁+2
  5. Complete analysis of 4-fold generalized theta graphs: Systematically studied all possible configurations in the m=4 case

Methodology Details

Problem Definition

Given a generalized theta graph Θ(s₁,s₂,...,sₘ), where:

  • Two central vertices c₁ and c₂
  • m internally disjoint paths Pᵢ with length sᵢ+1
  • Assume s₁ ≤ s₂ ≤ ... ≤ sₘ

Objective: Determine the metric dimension β(G) of the graph, i.e., the size of a minimum resolving set.

Core Theoretical Framework

1. Identical Paths Theorem

Theorem 3.3: Let graph G satisfy |IP(G)| = n, where IP(G) is the set of identical paths. Then: β(G)≥∑i=1n(mi−1)\beta(G) \geq \sum_{i=1}^n (m_i - 1)

The key idea of this theorem is: if the graph contains multiple internally disjoint paths of identical length connecting the same pair of vertices, at least one internal vertex from each of m-1 paths must be selected as a resolving vertex.

2. Mutually Distant Distance Concept

For vertices u and v, if u MD v and v MD u, denoted as u MMD v. This concept is used to analyze which vertex pairs are difficult to distinguish.

3. Path Resolution Strategy

Proposition 3.8: If M₁ ≠ M₂, then W = {w₁,w₂} can resolve path P, where Mᵢ is the set of vertices mutually maximally distant from wᵢ.

Technical Innovations

  1. Hierarchical Analysis Method: Decompose the resolution problem of generalized theta graphs into:
    • Resolution of internal vertices on paths
    • Resolution of vertices across different paths
    • Special treatment of central vertices
  2. Exploitation of Geometric Symmetry: Utilize the symmetry properties of generalized theta graphs by selecting resolving vertices at appropriate positions to break symmetry
  3. Parity Analysis: Systematically utilize the parity of path lengths to determine the construction of optimal resolving sets

Main Results

General Bounds

Theorem 1.2: For generalized theta graph Θ(s₁,s₂,...,sₘ), where m ≥ 2: m−3≤β(Θ(s1,s2,...,sm))≤mm-3 \leq \beta(\Theta(s_1,s_2,...,s_m)) \leq m

Uniform Case

Theorems 3.17-3.19: For uniform generalized theta graphs Θ(sᵐ):

m-1 & \text{if } m \geq 5 \text{ and } s \geq 2 \\ m-1 & \text{if } m = 4 \text{ and } s > 2 \\ m & \text{otherwise} \end{cases}$$ ### Theta Graphs (m=3) **Theorem 4.4**: $$\beta(\Theta(s_1,s_2,s_3)) = \begin{cases} 3 & \text{if } s_1=s_2=s_3 \text{ or } s_1=s_2 \text{ and } s_3=s_1+2 \\ 2 & \text{otherwise} \end{cases}$$ ### 4-fold Generalized Theta Graphs **Theorem 5.12**: For Θ(s₁,s₂,s₃,s₄): $$\beta(\Theta(s_1,s_2,s_3,s_4)) = \begin{cases} 4 & \text{for } \Theta(1^4), \Theta(1^3,3), \Theta(2^4), \Theta(2^3,4) \\ 2 & \text{if } s_2=s_1+1, s_2=s_3 \text{ and } s_4 \geq s_1+4 \\ 2 & \text{if } s_2=s_1+1 \text{ and } s_2 < s_3 \leq s_4 \\ 3 & \text{otherwise} \end{cases}$$ ## Proof Techniques ### Upper Bound Construction Prove upper bounds through explicit construction of resolving sets. Typical strategy: 1. Select central vertex c₁ 2. Select vertices at position ⌈sᵢ/2⌉ on each path Pᵢ (i≥2) 3. Verify that this set indeed resolves all vertex pairs ### Lower Bound Proofs Primarily use the following techniques: 1. **Identical Path Analysis**: Apply Theorem 3.3 2. **Proof by Contradiction**: Assume existence of a smaller resolving set and derive a contradiction 3. **Distance Vector Analysis**: Analyze the distance vector representation of vertices ### Special Case Handling For boundary cases, use exhaustive verification: - Check all possible resolving set configurations - Verify whether each configuration truly resolves all vertex pairs in the graph ## Related Work 1. **Historical Development**: Metric dimension was independently introduced by Slater and Harary-Melter in the 1970s 2. **Cycles**: Metric dimension is 2, completely solved 3. **Bicyclic Graph Classification**: - Type 1: Two cycles sharing a vertex - Type 2: Two disjoint cycles connected by a path - Type 3: Theta graphs (special case of the subject of this paper) 4. **Related Surveys**: References [5,8] provide comprehensive surveys of metric dimension research ## Conclusions and Discussion ### Main Conclusions 1. Established a complete theoretical framework for the metric dimension of generalized theta graphs 2. Proved that in most cases the metric dimension is close to the number of paths m 3. Identified special configurations where the metric dimension reaches the upper bound m 4. Provided new insights into the relationship between graph symmetry and metric dimension ### Limitations 1. **Computational Complexity**: Determining exact metric dimension remains difficult for large-scale graphs 2. **Special Cases**: Certain boundary cases require exhaustive verification, lacking unified theoretical treatment 3. **Generalizability**: Results are primarily tailored to theta graph structures with limited applicability to other graph classes ### Future Directions 1. Study more general multi-path graph structures 2. Develop efficient algorithms for metric dimension computation 3. Explore applications of metric dimension in network science 4. Investigate approximation algorithms and complexity theory for metric dimension ## In-Depth Evaluation ### Strengths 1. **Theoretical Completeness**: Provides systematic theoretical analysis of the metric dimension of generalized theta graphs 2. **Technical Innovation**: The Identical Paths Theorem provides a new analytical tool for related problems 3. **Exact Results**: Provides exact metric dimension formulas for multiple important subclasses 4. **Rigorous Proofs**: Mathematical proofs are detailed, rigorous, and logically clear ### Weaknesses 1. **Insufficient Application Focus**: Limited discussion of practical value of theoretical results 2. **Computational Aspects**: Lacks efficient algorithm implementation and complexity analysis 3. **Experimental Verification**: Primarily theoretical analysis without computational experiments ### Impact 1. **Theoretical Contribution**: Makes important contributions to graph metric dimension theory 2. **Methodological Value**: Proposed analytical techniques may be applicable to other graph classes 3. **Application Potential**: Has promising applications in network localization, robot navigation, and related fields ### Applicable Scenarios 1. Critical node selection in network topology design 2. Localization problems in sensor networks 3. Index design in graph databases 4. Feature identification in chemical molecular structures ## References The paper cites important literature in the field, including foundational works on metric dimension (Slater, Harary-Melter) and related survey papers, providing a solid theoretical foundation for the research.