Uniquely identifying the edges of a graph: the edge metric dimension

DOI10.1016/J.DAM.2018.05.052zbMATH Open1401.05166arXiv1602.00291OpenAlexW2963118757WikidataQ129613199 ScholiaQ129613199MaRDI QIDQ1627862FDOQ1627862

Authors: Aleksander Kelenc, Niko Tratnik, Ismael G. Yero 

Publication date: 3 December 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: Let $G=(V,E)$ be a connected graph, let $vinV$ be a vertex and let $e=uwinE$ 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 $winV$ distinguishes two edges $e_1,e_{2}inE$ if $d_G(w,e_1)e{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.

Full work available at URL: https://arxiv.org/abs/1602.00291

Recommendations

• On the edge dimension of a graph
• Graphs with the edge metric dimension smaller than the metric dimension
• On the edge metric dimension of graphs
• The dominant edge metric dimension of graphs
• Edge metric dimension of some graph operations

zbMATH Keywords

metric dimensionedge metric dimensionedge metric generator

Mathematics Subject Classification ID

Distance in graphs (05C12) Connectivity (05C40)

Cites Work

• Title not available (Why is that?)
• Approximation algorithms for combinatorial problems
• Resolvability in graphs and the metric dimension of a graph
• Base size, metric dimension and other invariants of groups and graphs
• On the metric dimension of some families of graphs
• On the Metric Dimension of Cartesian Products of Graphs
• Resolvability and the upper dimension of graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• On \(k\)-dimensional graphs and their bases
• Landmarks in graphs
• On the Complexity of Metric Dimension
• The local metric dimension of a graph
• Metric bases in digital geometry
• Structure-activity maps for visualizing the graph variables arising in drug design
• Resolving domination in graphs
• The independent resolving number of a graph
• The strong metric dimension of graphs and digraphs
• Extremal graph theory for metric dimension and diameter
• Title not available (Why is that?)
• On the metric dimension of infinite graphs
• The partition dimension of a graph
• On the strong partition dimension of graphs
• Title not available (Why is that?)

Cited In (72)

• The \(k\)-size edge metric dimension of graphs
• Edge metric dimension of some graph operations
• On the edge metric dimension of graphs
• Vertex and edge metric dimensions of unicyclic graphs
• Edge metric dimension of some generalized Petersen graphs
• On graphs with the maximum edge metric dimension
• On some plane graphs and their metric dimension
• Edge metric dimension of graphs.
• The comparative analysis of metric and edge metric dimension of some subdivisions of the wheel graph
• On the metric dimensions for sets of vertices
• The vertex-edge resolvability of some wheel-related graphs
• On the edge dimension and the fractional edge dimension of graphs
• On mixed metric dimension in subdivision, middle, and total graphs
• Determining the edge metric dimension of the generalized Petersen graph \(P(n, 3)\)
• Fault-tolerant edge metric dimension of certain families of graphs
• Extremal results for graphs of bounded metric dimension
• Metric dimension and edge metric dimension of windmill graphs
• On the edge metric dimension of convex polytopes and its related graphs
• Edge version of metric dimension and doubly resolving sets of the necklace graph
• Mixed metric dimension of some plane graphs
• The dominant edge metric dimension of graphs
• Metric dimensions vs. cyclomatic number of graphs with minimum degree at least two
• Mixed metric dimension of graphs with edge disjoint cycles
• Asymptotic behavior of the edge metric dimension of the random graph
• Bounds on metric dimensions of graphs with edge disjoint cycles
• Extremal mixed metric dimension with respect to the cyclomatic number
• Graphs with the edge metric dimension smaller than the metric dimension
• Optimal identification of sets of edges using 2-factors
• A note on the metric and edge metric dimensions of 2-connected graphs
• Fault-tolerant metric dimension of two-fold heptagonal-nonagonal circular ladder
• Edge metric dimensions via hierarchical product and integer linear programming
• Edge metric dimension and mixed metric dimension of planar graph \(Q_n\)
• Vertex and edge metric dimensions of cacti
• The effect of vertex and edge deletion on the edge metric dimension of graphs
• Further new results on strong resolving partitions for graphs
• Computation of edge resolvability of benzenoid tripod structure
• The mixed metric dimension of flower snarks and wheels
• On metric dimensions of hypercubes
• Some binary products and integer linear programming for \(k\)-metric dimension of graphs
• Local metric dimension of graphs: generalized hierarchical products and some applications
• Edge metric dimension of \(k\) multiwheel graph
• Metric dimension and pattern avoidance in graphs
• Link dimension and exact construction of graphs from distance vectors
• Mixed metric dimension of some graphs
• The difference between several metric dimension graph invariants
• The Edge Partition Dimension of Graphs
• \(l\)-clique metric dimension of graphs
• On a conjecture about the local metric dimension of graphs
• On approximation algorithm for the edge metric dimension problem
• On the edge dimension of a graph
• Title not available (Why is that?)
• Fractional local edge dimensions of a graph
• Resolving vertices of graphs with differences
• Edge version of metric dimension for the families of grid graphs and generalized prism graphs
• Edge-locating coloring of graphs
• Edge metric dimension of some Cartesian product of graphs
• Local edge metric dimensions via corona products and integer linear programming
• On the edge metric dimension and Wiener index of the blow up of graphs
• Locating parameters of the total graph of \(\Gamma(\mathbb{Z}_{2^np^m})\)
• Erdös-Gallai-type problems for distance-edge-monitoring numbers
• On the distance-edge-monitoring numbers of graphs
• Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications
• On symmetrical convex polytopes and their edge resolvability
• On mixed metric dimension of crystal cubic carbon structure
• Edge metric dimension and mixed metric dimension of a plane graph \(T_n\)
• Monitoring the edges of product networks using distances
• Realizability problem of distance-edge-monitoring numbers
• Metric Properties of Non-Commuting Graph Associated to Two Groups
• On approximation algorithm for the edge metric dimension problem
• Distance-based covering problems for graphs of given cyclomatic number
• Mixed metric dimension of some plane graphs
• Monitoring the edges of a graph using distances with given girth

This page was built for publication: Uniquely identifying the edges of a graph: the edge metric dimension

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1627862)