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

Basic Information

• Paper ID: 2105.07808
• Title: Local fractional metric dimension of rotationally symmetric planar graphs arisen from planar chorded cycles
• Authors: Shahbaz Ali, Raúl M. Falcón, Muhammad Khalid Mahmood
• Classification: math.CO (Combinatorics)
• Publication Date: May 17, 2021 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2105.07808

Abstract

This paper describes a new family of rotationally symmetric planar graphs constructed via edge amalgamation based on planar chorded cycles. For graphs generated by chorded cycles of order at most 6, the local fractional metric dimension is established. Through asymptotic behavior analysis, the existence of new families of rotationally symmetric planar graphs with constant or bounded local fractional metric dimension is ensured.

Research Background and Motivation

Problem Background

1. Origin of metric dimension problem: Independently introduced in the 1970s by Slater and Harary & Melter, aimed at determining the minimum number of vertices in a graph whose distance vectors uniquely represent all vertices
2. Problem complexity: The metric dimension problem is NP-hard, but explicit solutions have been obtained for different types of graphs
3. Practical application value: Important applications in robot navigation, pattern recognition, image processing, chemical compound representation, combinatorial optimization, and networking

Research Motivation

1. Theoretical requirement: Scholars such as Imran posed the problem of characterizing families of (rotationally symmetric) planar graphs with constant metric dimension
2. Technical development: In 2000, Chartrand et al. formulated the metric dimension problem as an integer programming problem; subsequently, Currie and Oellermann proposed linear programming relaxation, introducing the concept of fractional metric dimension
3. Localization research: In 2018, Benish et al. introduced the concept of local fractional metric dimension involving only adjacent vertices, a research area still in its infancy

Limitations of Existing Methods

1. Research on local fractional metric dimension is very limited, with explicit results for only a few graph types
2. Recent work by Liu et al. contains technical errors requiring comprehensive reanalysis
3. Lack of systematic research on graphs constructed from higher-order chorded cycles

Core Contributions

1. New graph family construction: Describes a new family of rotationally symmetric planar graphs $G_m(G)$ constructed via edge amalgamation of planar chorded cycles
2. Dimension calculation: Establishes the local fractional metric dimension for all rotationally symmetric planar graphs generated by planar chorded cycles of order $n ≤ 6$
3. Asymptotic analysis: Provides asymptotic behavior analysis of the local fractional metric dimension for these graph families
4. Theoretical correction: Corrects erroneous results in the literature regarding the local fractional metric dimension of wheel graphs
5. Classification completeness: Provides comprehensive analysis of all non-isomorphic cases for quadrilateral, pentagonal, and hexagonal chorded cycles

Methodology Details

Task Definition

Study the local fractional metric dimension of rotationally symmetric planar graphs $G_m(G)$, where $G$ is a planar chorded cycle of order $n$ and $m ≥ 2$ is the number of copies.

Graph Construction Method

Given $m$ disjoint copies $G_1, G_2, ..., G_m$ of a planar chorded cycle $G$, construct $G_m(G)$ through the following sequence of edge amalgamations:

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

The resulting graph $G_m(G)$ is a rotationally symmetric planar graph of order $m \cdot (n-2)$.

Core Concept Definitions

Local Fractional Metric Dimension

For a graph $G$, the local fractional metric dimension is defined as: $\text{ldim}_f(G) := \min\left\{\sum_{v \in V(G)} \vartheta(v) : \vartheta \text{ is a local resolving function of } G\right\}$

where a local resolving function $\vartheta: V(G) \to [0,1]$ satisfies: $\sum_{u \in R\{v,w\}} \vartheta(u) \geq 1$ for all adjacent vertex pairs $vw \in E(G)$.

Key Lemma

Lemma 2.1: For a finite connected graph $G$ of order $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$ if and only if $G$ is bipartite
• $\text{ldim}_f(G) = \frac{n}{2}$ if and only if every vertex in $V(G)$ has a true twin vertex

Technical Innovations

1. Systematic analysis: First comprehensive analysis of all rotationally symmetric graphs constructed from planar chorded cycles of order at most 6
2. Computational method: Solving local fractional metric dimension through linear programming to obtain exact values or bounds
3. Asymptotic analysis: Establishing asymptotic behavior patterns of local fractional metric dimension for various graph families
4. Error correction: Correcting erroneous results in reference 2 regarding the local fractional metric dimension of wheel graphs

Experimental Setup

Graph Classes Analyzed

The paper analyzes the following graph classes:

• Quadrilateral chorded cycles: Q₁, Q₂ (2 types)
• Pentagonal chorded cycles: P₁ to P₆ (6 types)
• Hexagonal chorded cycles: H₁ to H₁₇ (17 types)

Computational Methods

1. Linear programming: Constructing corresponding linear programming problems for each graph class
2. Symmetry exploitation: Utilizing rotational symmetry of graphs to simplify computation
3. Resolving neighborhood analysis: Computing the size of resolving neighborhoods $|R\{v,w\}|$ for critical edge pairs

Evaluation Metrics

• Exact values of local fractional metric dimension
• Asymptotic upper bounds
• Comparison with theoretical lower bounds

Experimental Results

Main Results

Quadrilateral Case

Proposition 3.1: For $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}$

Pentagonal Case

Theorem 4.1: Establishes upper bounds for the local fractional metric dimension of graphs constructed from all pentagonal chorded cycles $P_1$ to $P_6$, for example:

• $\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}$

Hexagonal Case

Theorem 4.2: For hexagonal chorded cycles $H_1$ to $H_{17}$:

• $\text{ldim}_f(G_m(H_1)) = \text{ldim}_f(G_m(H_2)) = 1$ (bipartite graphs)
• Other cases provide corresponding upper bound formulas

Corrected Wheel Graph Results

Lemma 3.1: For wheel graphs $W_n$ of order $n ≥ 4$: