Extremal graph theory for metric dimension and diameter

zbMATH Open1219.05051arXiv0705.0938MaRDI QIDQ2380462FDOQ2380462

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

Publication date: 26 March 2010

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

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.

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

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

zbMATH Keywords

graphdistancediametermetric dimensionorderresolving setmetric basis

Mathematics Subject Classification ID

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

Cited In (80)

• Title not available (Why is that?)
• Title not available (Why is that?)
• The doubly metric dimensions of cactus graphs and block graphs
• The local metric dimension of amalgamation of graphs
• Resolvability in complement of the intersection graph of annihilator submodules of a module
• The metric dimension of the zero-divisor graph of a matrix semiring
• \( [ 1 , 2 ]\)-dimension of graphs
• Redefining fractal cubic networks and determining their metric dimension and fault-tolerant metric dimension
• Metric dimension of ideal-intersection graph of the ring Zn
• Sharp bound on the truncated metric dimension of trees
• Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications
• Enhanced power graphs of certain non-abelian groups
• On distance-\(s\) locating and distance-\(t\) dominating sets in graphs
• Metric and strong metric dimension in commuting graphs of finite groups
• Title not available (Why is that?)
• Vertex identification in trees
• Wiener index and addressing of some finite graphs
• Fault-tolerance in distance-edge-monitoring sets
• On dimension of some finite total graphs
• Graphs with constant adjacency dimension
• Monitoring the edges of a graph using distances with given girth
• Fixing number and metric dimension of a zero-divisor graph associated with a ring
• Edge metric dimension of some graph operations
• On strong metric dimension of graphs and their complements
• A polynomial sized kernel for tracking paths problem
• The equidistant dimension of graphs
• Resolving sets for higher dimensional projective spaces
• On the connected metric dimension of graphs and their complements
• The threshold dimension and irreducible graphs
• The metric dimension of the enhanced power graph of a finite group
• The connectivity and the spectral radius of commuting graphs on certain finite groups
• Unicyclic graphs with non-isolated resolving number $2$
• On maximal det-independent (res-independent) sets in graphs
• On the structure of isoclinism classes of the non-commuting graphs
• On the edge dimension and the fractional edge dimension of graphs
• On the strong metric dimension of Cartesian and direct products of graphs
• The metric dimension for resolving several objects
• On the commuting graph of semidihedral group
• Uniquely identifying the edges of a graph: the edge metric dimension
• Bounds on the sum of domination number and metric dimension of graphs
• The fractional strong metric dimension in three graph products
• Extremal results for graphs of bounded metric dimension
• The metric dimension of the lexicographic product of graphs
• The simultaneous fractional dimension of graph families
• The difference between the metric dimension and the determining number of a graph
• Graphs with doubly resolving number 2
• On the metric dimension of infinite graphs
• Locating-dominating codes: bounds and extremal cardinalities
• Extremal metrics on graphs. I
• Resolving dominating partitions in graphs
• Metric Dimension for Amalgamations of Graphs
• On the fractional strong metric dimension of graphs
• Title not available (Why is that?)
• Variable neighborhood search for metric dimension and minimal doubly resolving set problems
• The fractional \(k\)-truncated metric dimension of graphs
• Maker-breaker resolving game
• On the limiting distribution of the metric dimension for random forests
• On vertices contained in all or in no metric basis
• On the number of resolving pairs in graphs
• The metric dimension & distance spectrum of non-commuting graph of dihedral group
• Truncated metric dimension for finite graphs
• Minimum partition of an \(r\)-independence system
• Twin vertices in fault-tolerant metric sets and fault-tolerant metric dimension of multistage interconnection networks
• Title not available (Why is that?)
• Title not available (Why is that?)
• Beyond Helly graphs: the diameter problem on absolute retracts
• Metric dimension and pattern avoidance in graphs
• The twin non-commuting graph of a group
• Bounding the Order of a Graph Using Its Diameter and Metric Dimension: A Study Through Tree Decompositions and VC Dimension
• Nordhaus-Gaddum bounds for locating domination
• Neighbor-locating colorings in graphs
• A bridge between the minimal doubly resolving set problem in (folded) hypercubes and the coin weighing problem
• On doubly resolving sets in graphs
• On the metric determination of linear dependence graph
• On graphs of order \(n\) with metric dimension \(n-4\)
• Metric dimension of maximal outerplanar graphs
• On the metric dimension of the reduced power graph of a finite group
• Diameter, minimum degree and hyperbolicity constant in graphs
• The threshold dimension of a graph
• Title not available (Why is that?)

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• The metric dimension and girth of graphs 👍 👎
• Diameter Bounds for Graph Extensions 👍 👎
• Extremal Graph Theory for Metric Dimension and Diameter 👍 👎
• Extremal metrics on graphs. I 👍 👎
• Extremal results for graphs of bounded metric dimension 👍 👎
• Estimates of the metric dimension of a graph in terms of its diameter and the number of vertices 👍 👎
• On graphs with the maximum edge metric dimension 👍 👎

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)