Extremal graph theory for metric dimension and diameter

MaRDI QIDQ2380462zbMATH OpenFDO

Authors C. Hernando, Mercè Mora, I. M. Pelayo, Carlos Seara, David R. Wood

Publication date 26 March 2010

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0705.0938, https://eudml.org/doc/233831, http://www.emis.de/journals/EJC/Volume_17/Abstracts/v17i1r30.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

diameterdistancegraphmetric basismetric dimensionorderresolving set

Mathematics Subject Classification ID

Distance in graphs (05C12) Extremal problems in graph theory (05C35)

Abstract: A set of vertices $S$ emph{resolves} a connected graph $G$ if every vertex is uniquely determined by its vector of distances to the vertices in $S$. The emph{metric dimension} of $G$ is the minimum cardinality of a resolving set of $G$. Let $$ be the set of graphs with metric dimension $$ and diameter $D$. It is well-known that the minimum order of a graph in $$ is exactly $$. The first contribution of this paper is to characterise the graphs in $$ with order $$ for all values of $$ and $D$. Such a characterisation was previously only known for $Dleq2$ or $$. The second contribution is to determine the maximum order of a graph in $$ for all values of $D$ and $$. Only a weak upper bound was previously known.

Review text

Summary: A set of vertices \(S\) resolves a connected graph \(G\) if every vertex is uniquely determined by its vector of distances to the vertices in \(S\). The metric dimension of \(G\) is the minimum cardinality of a resolving set of \(G\). Let \({\mathcal G}_{\beta,D}\) be the set of graphs with metric dimension \(\beta\) and diameter \(D\). It is well-known that the minimum order of a graph in \({\mathcal G}_{\beta,D}\) is exactly \(\beta+ D\). The first contribution of this paper is to characterise the graphs in \({\mathcal G}_{\beta,D}\) with order \(\beta+ D\) for all values of \(\beta\) and \(D\). Such a characterisation was previously only known for \(D\leq 2\) or \(\beta\leq 1\). The second contribution is to determine the maximum order of a graph in \({\mathcal G}_{\beta,D}\) for all values of \(D\) and \(\beta\). Only a weak upper bound was previously known.

Recommendations

• Extremal Graph Theory for Metric Dimension and Diameter
• Extremal results for graphs of bounded metric dimension
• On graphs with the maximum edge metric dimension
• Extremal metrics on graphs. I
• The metric dimension and girth of graphs
• Estimates of the metric dimension of a graph in terms of its diameter and the number of vertices
• Diameter Bounds for Graph Extensions
• scientific article; zbMATH DE number 975404
• scientific article; zbMATH DE number 2123255
• scientific article; zbMATH DE number 3841900

Cited in

(only showing first 100 items - show all)

• Resolvability in graphs and the metric dimension of a graph
• On the structure of isoclinism classes of the non-commuting graphs
• The fractional strong metric dimension in three graph products
• Uniquely identifying the edges of a graph: the edge metric dimension
• On the metric dimension of infinite graphs
• Variable neighborhood search for metric dimension and minimal doubly resolving set problems
• Edge metric dimension of some graph operations
• Resolving sets for higher dimensional projective spaces
• The threshold dimension of a graph
• Resolving dominating partitions in graphs
• Maker-breaker resolving game
• Metric dimension of maximal outerplanar graphs
• On the commuting graph of semidihedral group
• Extremal results for graphs of bounded metric dimension
• A bridge between the minimal doubly resolving set problem in (folded) hypercubes and the coin weighing problem
• On the metric dimension of the reduced power graph of a finite group
• On doubly resolving sets in graphs
• The threshold dimension and irreducible graphs
• On maximal det-independent (res-independent) sets in graphs
• The equidistant dimension of graphs
• The fractional \(k\)-truncated metric dimension of graphs
• On vertices contained in all or in no metric basis
• Truncated metric dimension for finite graphs
• The connected metric dimension at a vertex of a graph
• Neighbor-locating colorings in graphs
• On the limiting distribution of the metric dimension for random forests
• On strong metric dimension of graphs and their complements
• The metric dimension and girth of graphs
• Nordhaus-Gaddum bounds for locating domination
• On the metric dimension, the upper dimension and the resolving number of graphs
• The metric dimension for resolving several objects
• Minimum partition of an \(r\)-independence system
• Twin vertices in fault-tolerant metric sets and fault-tolerant metric dimension of multistage interconnection networks
• Beyond Helly graphs: the diameter problem on absolute retracts
• On graphs of order \(n\) with metric dimension \(n-4\)
• Extremal metrics on graphs. I
• On the metric dimension of infinite graphs
• Metric dimension for amalgamations of graphs
• A comparison on metric dimension of graphs, line graphs, and line graphs of the subdivision graphs
• The difference between the metric dimension and the determining number of a graph
• Graphs with same diameter and metric dimension
• On the fractional strong metric dimension of graphs
• Extremal Graph Theory for Metric Dimension and Diameter
• Graphs of maximum and minimum order with fixed metric dimension and diameter
• On the strong metric dimension of Cartesian and direct products of graphs
• Bounds on the sum of domination number and metric dimension of graphs
• Bounding the order of a graph using its diameter and metric dimension: a study through tree decompositions and VC dimension
• Fixing number and metric dimension of a zero-divisor graph associated with a ring
• The metric dimension of the enhanced power graph of a finite group
• Resolvability in complement of the intersection graph of annihilator submodules of a module
• The connectivity and the spectral radius of commuting graphs on certain finite groups
• Metric dimension of ideal-intersection graph of the ring \(\mathbb{Z}_n\)
• On the connected metric dimension of graphs and their complements
• The metric dimension \& distance spectrum of non-commuting graph of dihedral group
• Unicyclic graphs with non-isolated resolving number $2$
• Vertex identification in trees
• Graphs with constant adjacency dimension
• scientific article; zbMATH DE number 7560302 (Why is no real title available?)
• Diameter, minimum degree and hyperbolicity constant in graphs
• scientific article; zbMATH DE number 975404 (Why is no real title available?)
• scientific article; zbMATH DE number 7589564 (Why is no real title available?)
• Metric and strong metric dimension in commuting graphs of finite groups
• scientific article; zbMATH DE number 7666856 (Why is no real title available?)
• On lower bounds for the metric dimension of graphs
• The metric dimension of the lexicographic product of graphs
• A polynomial sized kernel for tracking paths problem
• Sharp bound on the truncated metric dimension of trees
• On the edge dimension and the fractional edge dimension of graphs
• Graphs with doubly resolving number 2
• Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications
• On the metric determination of linear dependence graph
• The simultaneous fractional dimension of graph families
• The metric dimension of the zero-divisor graph of a matrix semiring
• Redefining fractal cubic networks and determining their metric dimension and fault-tolerant metric dimension
• Wiener index and addressing of some finite graphs
• Metric dimension of lexicographic product of some known graphs
• Monitoring the edges of a graph using distances with given girth
• \( [ 1 , 2 ]\)-dimension of graphs
• scientific article; zbMATH DE number 7720720 (Why is no real title available?)
• On dimension of some finite total graphs
• The doubly metric dimensions of cactus graphs and block graphs
• The local metric dimension of amalgamation of graphs
• Metric dimension and \(R\)-sets of connected graphs
• On distance-s locating and distance-t dominating sets in graphs
• Enhanced power graphs of certain non-abelian groups
• Fault-tolerance in distance-edge-monitoring sets
• Fault tolerance for metric dimension and its variants
• Graph identification index
• Some symmetrical planar structures with their fault-tolerant metric dimension
• On some metric properties of supertoken graphs
• Properties of commuting graphs over finite non-abelian groups
• Metric dimensions of generalized Sierpiński graphs over squares
• Improvements in nonlocal metric dimension bounds
• The metric dimension of the total graph of a semiring
• On the simultaneous metric dimension of a graph and its complement
• A study of a combination of distance domination and resolvability in graphs
• Metric dimension and diameter in bipartite graphs
• Metric and strong metric dimension in intersection power graphs of finite groups
• Throttling for metric dimension and its variants
• The doubly resolving number of the lexicographic product of graphs

This page was built for publication: Extremal graph theory for metric dimension and diameter

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