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

DOI10.1016/J.DAM.2018.05.052MaRDI QIDQ1627862zbMATH OpenOpenAlexWikidataFDO

Authors Aleksander Kelenc, Niko Tratnik, Ismael G. Yero

Publication date 3 December 2018

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

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

zbMATH Keywords

metric dimensionedge metric dimensionedge metric generator

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(72)

• On the edge dimension of a graph
• The \(k\)-size edge metric dimension of graphs
• Edge metric dimension of some graph operations
• Monitoring the edges of a graph using distances with given girth
• Mixed metric dimension of some plane graphs
• scientific article; zbMATH DE number 7560302 (Why is no real title available?)
• Fractional local edge dimensions of a graph
• 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
• Resolving vertices of graphs with differences
• On some plane graphs and their metric dimension
• Edge version of metric dimension for the families of grid graphs and generalized prism graphs
• Edge metric dimension of graphs.
• Edge-locating coloring of graphs
• On the metric dimensions for sets of vertices
• The comparative analysis of metric and edge metric dimension of some subdivisions of the wheel graph
• The vertex-edge resolvability of some wheel-related graphs
• Determining the edge metric dimension of the generalized Petersen graph \(P(n, 3)\)
• On the edge dimension and the fractional edge dimension of graphs
• On mixed metric dimension in subdivision, middle, and total graphs
• Fault-tolerant edge metric dimension of certain families of graphs
• Edge metric dimension of some Cartesian product of graphs
• Local edge metric dimensions via corona products and integer linear programming
• Extremal results for graphs of bounded metric dimension
• Metric dimension and edge metric dimension of windmill graphs
• Edge version of metric dimension and doubly resolving sets of the necklace graph
• On the edge metric dimension of convex polytopes and its related graphs
• On the edge metric dimension and Wiener index of the blow up of graphs
• 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
• Locating parameters of the total graph of \(\Gamma(\mathbb{Z}_{2^np^m})\)
• 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
• Erdös-Gallai-type problems for distance-edge-monitoring numbers
• On the distance-edge-monitoring numbers of graphs
• Optimal identification of sets of edges using 2-factors
• 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
• 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
• On mixed metric dimension of crystal cubic carbon structure
• 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
• Some binary products and integer linear programming for \(k\)-metric dimension of graphs
• Local metric dimension of graphs: generalized hierarchical products and some applications
• On metric dimensions of hypercubes
• Edge metric dimension and mixed metric dimension of a plane graph \(T_n\)
• Edge metric dimension of \(k\) multiwheel graph
• Metric dimension and pattern avoidance in graphs
• Link dimension and exact construction of graphs from distance vectors
• Monitoring the edges of product networks using distances
• Mixed metric dimension of some graphs
• Realizability problem of distance-edge-monitoring numbers
• The difference between several metric dimension graph invariants
• 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
• Metric Properties of Non-Commuting Graph Associated to Two Groups
• The Edge Partition Dimension of Graphs
• On approximation algorithm for the edge metric dimension problem
• Distance-based covering problems for graphs of given cyclomatic number

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)