On the edge dimension of a graph
From MaRDI portal
Publication:1752687
DOI10.1016/J.DISC.2018.04.010zbMath1387.05073arXiv1611.01904OpenAlexW2802116907MaRDI QIDQ1752687
Publication date: 24 May 2018
Published in: Discrete Mathematics (Search for Journal in Brave)
Abstract: Given a connected graph $G(V, E)$, the edge dimension, denoted $mathrm{edim}(G)$, is the least size of a set $S subseteq V$ that distinguishes every pair of edges of $G$, in the sense that the edges have pairwise distinct tuples of distances to the vertices of $S$. The notation was introduced by Kelenc, Tratnik, and Yero, and in their paper, they asked several questions about properties of $mathrm{edim}$. In this article we answer two of these questions: we classify the graphs for which $mathrm{edim}(G) = n-1$ and show that $frac{mathrm{edim}(G)}{dim(G)}$ isn't bounded from above (here $dim(G)$ is the standard metric dimension of $G$). We also compute $mathrm{edim}(GBox P_m)$ and $mathrm{edim}(G + K_1)$.
Full work available at URL: https://arxiv.org/abs/1611.01904
Cites Work
- Unnamed Item
- Unnamed Item
- Resolvability and the upper dimension of graphs
- Resolvability in graphs and the metric dimension of a graph
- Uniquely identifying the edges of a graph: the edge metric dimension
- Landmarks in graphs
- On the Metric Dimension of Cartesian Products of Graphs
- Metric bases in digital geometry
- Structure-activity maps for visualizing the graph variables arising in drug design
Related Items (46)
On the adjacency dimension of graphs ⋮ Determining the edge metric dimension of the generalized Petersen graph \(P(n, 3)\) ⋮ Vertex and edge metric dimensions of unicyclic graphs ⋮ On the edge metric dimension of graphs ⋮ Fault-tolerant edge metric dimension of certain families of graphs ⋮ Expectation of the largest bet size in the Labouchere system ⋮ Metric dimensions vs. cyclomatic number of graphs with minimum degree at least two ⋮ On the edge metric dimension and Wiener index of the blow up of graphs ⋮ A note on the metric and edge metric dimensions of 2-connected graphs ⋮ Vertex and edge metric dimensions of cacti ⋮ Truncated metric dimension for finite graphs ⋮ Edge metric dimension and mixed metric dimension of planar graph \(Q_n\) ⋮ The effect of vertex and edge deletion on the edge metric dimension of graphs ⋮ Metric dimension and edge metric dimension of windmill graphs ⋮ On the edge dimension and the fractional edge dimension of graphs ⋮ Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications ⋮ Mixed metric dimension of some plane graphs ⋮ Locating parameters of the total graph of \(\Gamma(\mathbb{Z}_{2^np^m})\) ⋮ Edge metric dimension of \(k\) multiwheel graph ⋮ Unnamed Item ⋮ Mixed metric dimension of some graphs ⋮ Mixed metric dimension of some plane graphs ⋮ On gaps in the closures of images of divisor functions ⋮ On approximation algorithm for the edge metric dimension problem ⋮ On graphs with the maximum edge metric dimension ⋮ Asymptotic behavior of the edge metric dimension of the random graph ⋮ Bounds on metric dimensions of graphs with edge disjoint cycles ⋮ Graphs with the edge metric dimension smaller than the metric dimension ⋮ Edge metric dimension of some graph operations ⋮ Extremal mixed metric dimension with respect to the cyclomatic number ⋮ Unnamed Item ⋮ Edge metric dimension of some generalized Petersen graphs ⋮ Mixed metric dimension of graphs with edge disjoint cycles ⋮ Ranges of Unitary Divisor Functions ⋮ Distance-based covering problems for graphs of given cyclomatic number ⋮ Fractional local edge dimensions of a graph ⋮ 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 of convex polytopes and its related graphs ⋮ On symmetrical convex polytopes and their edge resolvability ⋮ Edge metric dimension and mixed metric dimension of a plane graph \(T_n\) ⋮ Edge metric dimensions via hierarchical product and integer linear programming ⋮ Extremal results for graphs of bounded metric dimension ⋮ The comparative analysis of metric and edge metric dimension of some subdivisions of the wheel graph ⋮ Metric dimension and pattern avoidance in graphs ⋮ Fault-tolerant metric dimension of two-fold heptagonal-nonagonal circular ladder
This page was built for publication: On the edge dimension of a graph
