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

Dimensión Métrica de Grafos Theta Generalizados

Información Básica

  • ID del Artículo: 2510.12100
  • Título: Metric Dimension of Generalized Theta Graphs
  • Autores: Nadia Benakli, Nicole Froitzheim, David Martinez
  • Clasificación: math.CO (Matemática Combinatoria)
  • Fecha de Publicación: 14 de octubre de 2025 (preimpresión arXiv)
  • Enlace del Artículo: https://arxiv.org/abs/2510.12100

Resumen

Este artículo investiga el problema de la dimensión métrica de grafos theta generalizados. Para un vértice w en el grafo G, se dice que w puede distinguir los vértices u y v si d(w,u)≠d(w,v). Si un conjunto de vértices W puede distinguir cada par de vértices distintos en el grafo, entonces W se denomina conjunto resolutivo. La dimensión métrica del grafo G es la cardinalidad del conjunto resolutivo mínimo. Este artículo estudia profundamente la dimensión métrica de grafos theta generalizados, proporcionando valores exactos e insights estructurales para múltiples subclases.

Antecedentes de Investigación y Motivación

  1. Problema Central: La dimensión métrica es un invariante importante en teoría de grafos, utilizado para distinguir vértices en un grafo basándose en sus distancias a un subconjunto fijo de vértices. Este artículo se especializa en el estudio de la dimensión métrica de grafos theta generalizados, una clase especial de grafos.
  2. Significado Práctico: La dimensión métrica tiene aplicaciones prácticas en múltiples disciplinas, incluyendo:
    • Navegación robótica
    • Localización en redes
    • Identificación de estructuras químicas
  3. Limitaciones de la Investigación Existente:
    • La dimensión métrica de grafos cíclicos es conocida como 2
    • La dimensión métrica de grafos unicíclicos ha sido determinada
    • Los grafos bicíclicos se dividen en tres tipos, de los cuales los grafos theta (Tipo 3) tienen resultados parciales conocidos
    • Sin embargo, la investigación sobre la dimensión métrica de grafos theta generalizados (con más de 3 caminos) es insuficiente
  4. Motivación de la Investigación: Los grafos theta generalizados son una extensión natural de los grafos cíclicos, formados por dos vértices conectados mediante múltiples caminos internamente disjuntos. Comprender su dimensión métrica es importante tanto para el desarrollo de la teoría de grafos como para aplicaciones prácticas.

Contribuciones Principales

  1. Establecimiento de límites generales para la dimensión métrica de grafos theta generalizados: Para Θ(s₁,s₂,...,sₘ), se demuestra que m-3 ≤ β(G) ≤ m
  2. Proposición y demostración del Teorema de Caminos Idénticos (Identical Paths Theorem): Proporciona un límite inferior para la dimensión métrica de la clase de grafos con caminos internamente disjuntos de igual longitud
  3. Obtención de la dimensión métrica exacta para múltiples subclases importantes:
    • Grafos theta generalizados uniformes Θ(sᵐ)
    • Grafos theta generalizados consecutivos (longitudes de caminos consecutivas)
    • Grafos theta generalizados con configuraciones especiales
  4. Proporcionar una nueva demostración de la dimensión métrica de grafos theta (m=3): Se redemuestra el resultado conocido β(Θ(s₁,s₂,s₃)) = 3 si y solo si todos los sᵢ son iguales o s₁=s₂ y s₃=s₁+2
  5. Análisis completo de grafos theta generalizados cuádruples: Investigación sistemática de todas las configuraciones posibles en el caso m=4

Explicación Detallada de Métodos

Definición de la Tarea

Dado un grafo theta generalizado Θ(s₁,s₂,...,sₘ), donde:

  • Dos vértices centrales c₁ y c₂
  • m caminos internamente disjuntos Pᵢ de longitud sᵢ+1
  • Se asume s₁ ≤ s₂ ≤ ... ≤ sₘ

Objetivo: Determinar la dimensión métrica β(G) del grafo, es decir, el tamaño del conjunto resolutivo mínimo.

Marco Teórico Central

1. Teorema de Caminos Idénticos (Identical Paths Theorem)

Teorema 3.3: Sea G un grafo tal que |IP(G)| = n, donde IP(G) es el conjunto de caminos idénticos, entonces: β(G)≥∑i=1n(mi−1)\beta(G) \geq \sum_{i=1}^n (m_i - 1)

La idea clave de este teorema es que si existen múltiples caminos internamente disjuntos de igual longitud conectando el mismo par de vértices, entonces debe seleccionarse al menos un vértice interno en m-1 caminos como vértice resolutivo.

2. Concepto de Distancia Mutuamente Máxima

Para los vértices u y v, si u MD v y v MD u, se denota como u MMD v. Este concepto se utiliza para analizar qué pares de vértices son difíciles de distinguir.

3. Estrategia de Resolución de Caminos

Proposición 3.8: Si M₁ ≠ M₂, entonces W = {w₁,w₂} puede resolver el camino P, donde Mᵢ es el conjunto de vértices con distancia mutuamente máxima respecto a wᵢ.

Puntos de Innovación Técnica

  1. Método de Análisis Estratificado: Descomposición del problema de resolución de grafos theta generalizados en:
    • Resolución de vértices internos en caminos
    • Resolución de vértices entre diferentes caminos
    • Tratamiento especial de vértices centrales
  2. Utilización de Simetría Geométrica: Aprovechamiento de las propiedades de simetría de grafos theta generalizados mediante la selección de vértices resolutivos en posiciones apropiadas para romper la simetría
  3. Análisis de Paridad: Utilización sistemática de la paridad de las longitudes de caminos para determinar la construcción óptima del conjunto resolutivo

Resultados Principales

Límites Generales

Teorema 1.2: Para un grafo theta generalizado Θ(s₁,s₂,...,sₘ), donde m ≥ 2: m−3≤β(Θ(s1,s2,...,sm))≤mm-3 \leq \beta(\Theta(s_1,s_2,...,s_m)) \leq m

Caso Uniforme

Teoremas 3.17-3.19: Para grafos theta generalizados uniformes Θ(sᵐ):

undefined