Dimensión métrica fraccionaria local de grafos planares simétricamente rotacionales surgidos de ciclos planares acordados

Información Básica

• ID del Artículo: 2105.07808
• Título: Local fractional metric dimension of rotationally symmetric planar graphs arisen from planar chorded cycles
• Autores: Shahbaz Ali, Raúl M. Falcón, Muhammad Khalid Mahmood
• Clasificación: math.CO (Matemática Combinatoria)
• Fecha de Publicación: 17 de mayo de 2021 (preimpresión arXiv)
• Enlace del Artículo: https://arxiv.org/abs/2105.07808

Resumen

Este artículo describe una nueva familia de grafos planares simétricamente rotacionales basada en una construcción de fusión de aristas de ciclos planares acordados. Para grafos generados por ciclos acordados de orden no superior a 6, se establece su dimensión métrica fraccionaria local. Mediante el análisis de su comportamiento asintótico, se asegura la existencia de nuevas familias de grafos planares simétricamente rotacionales con dimensión métrica fraccionaria local constante o acotada.

Antecedentes de Investigación y Motivación

Contexto del Problema

1. Origen del problema de dimensión métrica: Introducido independientemente en los años 70 por Slater y por Harary & Melter, con el objetivo de determinar la cantidad mínima de vértices cuya distancia vectorial puede representar de manera única los vértices en un grafo
2. Complejidad del problema: El problema de dimensión métrica es NP-difícil, aunque se han obtenido soluciones explícitas para diferentes tipos de grafos
3. Valor de aplicación práctica: Tiene aplicaciones importantes en navegación robótica, reconocimiento de patrones, procesamiento de imágenes, representación de compuestos químicos, optimización combinatoria y redes

Motivación de la Investigación

1. Necesidad teórica: Investigadores como Imran han planteado el problema de caracterizar familias de grafos planares (simétricamente rotacionales) con dimensión métrica constante
2. Desarrollo técnico: En 2000, Chartrand et al. formularon el problema de dimensión métrica como un problema de programación entera; posteriormente, Currie y Oellermann propusieron una relajación de programación lineal, introduciendo el concepto de dimensión métrica fraccionaria
3. Investigación localizada: En 2018, Benish et al. introdujeron el concepto de dimensión métrica fraccionaria local que solo involucra vértices adyacentes; este campo de investigación aún se encuentra en etapas iniciales

Limitaciones de Métodos Existentes

1. La investigación de dimensión métrica fraccionaria local es muy limitada, con resultados explícitos solo para pocos tipos de grafos
2. El trabajo reciente de Liu et al. contiene errores técnicos que requieren un reanálisis exhaustivo
3. Falta investigación sistemática de grafos construidos a partir de ciclos acordados de orden superior

Contribuciones Principales

1. Construcción de nueva familia de grafos: Se describe una nueva familia de grafos planares simétricamente rotacionales $G_m(G)$ basada en fusión de aristas de ciclos planares acordados
2. Cálculo de dimensión: Se establece la dimensión métrica fraccionaria local de todos los grafos planares simétricamente rotacionales generados por ciclos planares acordados de orden $n ≤ 6$
3. Análisis asintótico: Se proporciona análisis del comportamiento asintótico de la dimensión métrica fraccionaria local de estas familias de grafos
4. Corrección teórica: Se corrigen resultados erróneos en la literatura sobre la dimensión métrica fraccionaria local de grafos de rueda
5. Completitud de clasificación: Se realiza análisis exhaustivo de todos los casos no isomorfos de ciclos acordados cuadriláteros, pentagonales y hexagonales

Explicación Detallada de Métodos

Definición de Tareas

Investigar la dimensión métrica fraccionaria local de grafos planares simétricamente rotacionales $G_m(G)$, donde $G$ es un ciclo planar acordado de orden $n$ y $m ≥ 2$ es la cantidad de copias.

Método de Construcción de Grafos

Dadas $m$ copias disjuntas $G_1, G_2, ..., G_m$ de un ciclo planar acordado $G$, se construye $G_m(G)$ mediante la siguiente secuencia de fusiones de aristas:

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})$, para $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)$

El grafo resultante $G_m(G)$ es un grafo planar simétricamente rotacional de orden $m \cdot (n-2)$.

Definiciones de Conceptos Principales

Dimensión Métrica Fraccionaria Local

Para un grafo $G$, la dimensión métrica fraccionaria local se define como: $\text{ldim}_f(G) := \min\left\{\sum_{v \in V(G)} \vartheta(v) : \vartheta \text{ es una función resolvente local de } G\right\}$

donde una función resolvente local $\vartheta: V(G) \to [0,1]$ satisface: $\sum_{u \in R\{v,w\}} \vartheta(u) \geq 1$ para todos los pares de vértices adyacentes $vw \in E(G)$.

Lema Clave

Lema 2.1: Para un grafo finito conexo $G$ de orden $n ≥ 2$:

• $\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$ si y solo si $G$ es bipartito
• $\text{ldim}_f(G) = \frac{n}{2}$ si y solo si cada vértice en $V(G)$ tiene un verdadero gemelo

Puntos de Innovación Técnica

1. Análisis sistemático: Primer análisis exhaustivo de todos los grafos planares simétricamente rotacionales construidos a partir de ciclos acordados de orden no superior a 6
2. Método de cálculo: Resolución de la dimensión métrica fraccionaria local mediante programación lineal para obtener valores exactos o cotas superiores
3. Análisis asintótico: Establecimiento de patrones de comportamiento asintótico de la dimensión métrica fraccionaria local para varias familias de grafos
4. Corrección de errores: Corrección de resultados erróneos en la referencia 2 sobre la dimensión métrica fraccionaria local de grafos de rueda

Configuración Experimental

Análisis de Clases de Grafos

El artículo analiza las siguientes clases de grafos:

• Ciclos acordados cuadriláteros: Q₁, Q₂ (2 tipos)
• Ciclos acordados pentagonales: P₁ a P₆ (6 tipos)
• Ciclos acordados hexagonales: H₁ a H₁₇ (17 tipos)

Método de Cálculo

1. Programación lineal: Construcción de problemas de programación lineal correspondientes para cada clase de grafo
2. Utilización de simetría: Aprovechamiento de la simetría rotacional del grafo para simplificar cálculos
3. Análisis de vecindario resolvente: Cálculo del tamaño del vecindario resolvente $|R\{v,w\}|$ para pares de aristas críticas

Indicadores de Evaluación

• Valores exactos de dimensión métrica fraccionaria local
• Cotas superiores asintóticas
• Comparación con cotas inferiores teóricas

Resultados Experimentales

Resultados Principales

Caso Cuadrilátero

Proposición 3.1: Para $m ≥ 2$:

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

Caso Pentagonal

Teorema 4.1: Se establecen cotas superiores de dimensión métrica fraccionaria local para todos los ciclos acordados pentagonales $P_1$ a $P_6$, por ejemplo:

• $\text{ldim}_f(G_m(P_2)) \leq \begin{cases} \frac{2m}{m+1}, & \text{si } m \text{ es impar} \\ \frac{6m}{3m+2}, & \text{en otro caso} \end{cases}$

Caso Hexagonal

Teorema 4.2: Para ciclos acordados hexagonales $H_1$ a $H_{17}$:

• $\text{ldim}_f(G_m(H_1)) = \text{ldim}_f(G_m(H_2)) = 1$ (grafos bipartitos)
• Para otros casos se proporcionan fórmulas de cotas superiores correspondientes

Resultados Corregidos de Grafos de Rueda

Lema 3.1: Para grafos de rueda $W_n$ de orden $n ≥ 4$: