Source-linked AI summary
Uniquely identifying the edges of a graph: the edge metric dimension
Aleksander Kelenc, Niko Tratnik, Ismael G. Yero
TL;DR
The paper addresses how to uniquely identify graph edges when standard metric generators may not identify them. It introduces edge metric dimension, compares it with standard metric dimension, and studies realizability, complexity, approximation, bounds, and graph-family formulae. The authors prove NP-hardness, obtain an O(log m) polynomial-time approximation, and establish results for several graph classes while leaving some realization cases open.
Problem
Standard metric bases can identify all vertices without uniquely recognizing every edge, motivating a separate edge-focused metric parameter.
Method
The paper defines edge metric generators and edge metric dimension, then studies their relationship with standard metric dimension, realizability, complexity, approximation, bounds, and graph families.
Results
The authors prove that computing edge metric dimension for connected graphs is NP-hard, give an O(log m) polynomial-time approximation, and derive realizability and graph-family results.
Takeaways & Limitations
Edge metric dimension provides a distinct framework for studying edge identification and its relationship with standard metric dimension in connected graphs.
Takeaways & Limitations
Realization remains open for some prescribed triples with dim(G) < edim(G) and for general triples with edim(G) < dim(G).
Abstract
from arXiv · showhide
Let $G=(V,E)$ be a connected graph, let $v\in V$ be a vertex and let $e=uw\in E$ be an edge. The distance between the vertex $v$ and the edge $e$ is given by $d_G(e,v)=\min\{d_G(u,v),d_G(w,v)\}$. A vertex $w\in V$ distinguishes two edges $e_1,e_2\in E$ if $d_G(w,e_1)\ne d_G(w,e_2)$. A set $S$ of vertices in a connected graph $G$ is an edge metric generator for $G$ if every two edges of $G$ are distinguished by some vertex of $S$. The smallest cardinality of an edge metric generator for $G$ is called the edge metric dimension and is denoted by $edim(G)$. In this article we introduce the concept of edge metric dimension and initiate the study of its mathematical properties. We make a comparison between the edge metric dimension and the standard metric dimension of graphs while presenting some realization results concerning the edge metric dimension and the standard metric dimension of graphs. We prove that computing the edge metric dimension of connected graphs is NP-hard and give some approximation results. Moreover, we present some bounds and closed formulae for the edge metric dimension of several classes of graphs.
1 Introduction
The paper introduces edge metric generators to uniquely identify graph edges, addressing cases where standard metric bases fail to recognize every edge. It defines the edge metric dimension and studies its relationship with standard metric dimension, computational complexity, and graph classes.
- Metric generators identify points by their distances from a selected set of points.
- Figure 1 shows a graph where no metric basis uniquely recognizes all edges.
- Each metric basis in the example leaves at least one pair of edges indistinguished.
- The paper defines edge-to-vertex distance as the minimum distance from the vertex to either endpoint of the edge.
- An edge metric generator distinguishes every pair of edges, and the smallest such set has edge metric dimension edim(G).
- The study compares edge and standard metric dimensions, including Q4, where dim(Q4) = 4 and edim(Q4) = 3.
2 Edge metric generators and metric generators
The paper introduces edge metric dimension to identify graph edges by distances and compares it with standard metric dimension across graph families and realization problems. It gives exact values for several classes and constructs graphs exhibiting equality or strict differences between the two parameters.
- Realization results: The edge metric dimension is realizable at every value r with 1 ≤ r ≤ n − 1 for connected graphs of order n.Paths and complete graphs handle the boundary cases; a constructed tree handles intermediate values.
- Equal parameters: Grid graphs, paths, cycles, complete graphs, and complete bipartite graphs satisfy edim(G) = dim(G).For grids edim(G) = dim(G) = 2; for paths, cycles, and complete graphs the common values are 1, 2, and n − 1, respectively.
- Strict inequalities: Wheel graphs and fan graphs generally have edge metric dimension strictly larger than metric dimension.For wheels, the exception is W1,3; for fans, the stated exceptions are F1,1 and F1,2.
- Exact formulas: The paper also establishes edim(C4r□C4t) = 3 for all positive integers r and t.The proof supplies an edge metric generator of size three and shows that two vertices cannot suffice.
- Realization results: For any integers r and t with 2 ≤ r ≤ t ≤ 2r ≤ n − 2, some connected graph of order n has dim(G) = r and edim(G) = t.The construction uses graphs whose metric generators require r vertices while edge metric generators require t vertices.
- Strict inequalities: For every q ≥ 1, there exists a connected graph with edim(G) − dim(G) ≥ q.Thus, the gap between the two parameters can be arbitrarily large.
3 Complexity issues
The paper proves that deciding the edge metric dimension is NP-complete via a polynomial reduction from 3-SAT, and finding it is NP-hard. It also gives a polynomial-time O(log m)-factor approximation through set cover.
- Complexity of EDIM: The EDIM decision problem asks whether a connected graph G has an edge metric generator of size at most r.The problem instance consists of a connected graph and an integer threshold.
- NP-completeness reduction: 3-SAT is reduced to EDIM by constructing a connected graph whose edge metric dimension is at most r exactly when the formula is satisfiable.The construction uses truth-setting and satisfaction-testing components linked by communication, neutralizing, and correcting edges.
- NP-completeness reduction: r = 2m + n is the lower bound enforced for the constructed graph, where m is the number of clauses and n is the number of variables.Claims in the reduction establish edim(G) ≥ r, while a satisfying assignment yields an edge metric generator of size r.
- NP-completeness reduction: The reduction's two directions show that satisfiability implies edge metric dimension r and edge metric dimension r implies satisfiability.Together these lemmas complete the polynomial transformation and establish NP-completeness.
- Approximation: The edge metric dimension of a connected graph with m edges can be approximated in polynomial time within a factor of O(log m).The paper transforms the problem to set cover and applies the set-cover approximation algorithm.
4 Some bounds and closed formulae
This section develops structural bounds and characterizations for edge metric dimension, including extremal cases and results for hypercubes. It also contrasts the difficulty of equality characterization with standard metric dimension.
- General bounds: edim(G) is at least n−2 for every connected graph of order n, while any set V(G)−{v} is an edge metric generator.The lower bound follows because two omitted vertices would create indistinguishable edges incident with a common omitted vertex.
- Extremal graphs: If edim(G) = n−1, then every pair of distinct vertices has a common neighbor.Conversely, two vertices with disjoint neighborhoods yield an edge metric generator of size n−2.
- Extremal graphs: A universal vertex forces edim(G) to be either n−1 or n−2, and maximum-degree examples show that edim(G) = n−1 need not require degree n−1.The circulant graph CR(6, 2) has maximum degree strictly below n−1 while attaining edge metric dimension n−1.
- Extremal graphs: A connected graph with two vertices of degree n−1 has edim(G) = n−1.The proof shows that every candidate set omitting two vertices leaves two incident edges with identical distance representations.
- General bounds: For an edge metric basis S of size k, no basis vertex has degree greater than 2k−1, and |E(G)| ≤ (D + 1)k when G has diameter D.These bounds arise because each basis vertex yields limited distance values for incident edges, while all edge distances lie between 0 and D.
- Hypercubes: The n-dimensional hypercube satisfies edim(Q_n) ≤ n, using the n-vertex set B_n consisting of the all-one vector and vectors with one zero coordinate.The paper proves that B_n distinguishes every pair of distinct hypercube edges.
5 Conclusion
The paper concludes by establishing edge metric dimension as a new graph invariant and identifying several directions for further comparison, realization, characterization, and computation.
- Conclusion: The paper introduces edge metric dimension and initiates its study through realization results and comparisons with standard metric dimension.The conclusion frames these as central contributions of the work.
- Conclusion: Computing edge metric dimension for connected graphs is NP-hard, and the paper also obtains values or bounds for several graph families.The hardness result is obtained by a polynomial reduction from 3-SAT.
- Open problems: Open problems concern realization triplets, bounds between edim(G) and dim(G), equality cases, graphs with edim(G) < dim(G), outerplanar complexity, and edim(G) = n−1.These questions define the paper’s proposed continuation of the subject.