Source-linked AI summary
Extremal Graph Theory for Metric Dimension and Diameter
Carmen Hernando, Merce Mora, Ignacio M. Pelayo, Carlos Seara, David R. Wood
TL;DR
The paper studies the minimum- and maximum-order extremal questions for connected graphs with fixed metric dimension β and diameter D, addressing gaps in prior characterizations and upper bounds. It characterizes all graphs of order β+D and determines the exact maximum order for every D and β.
Problem
The paper examines the minimum- and maximum-order questions for connected graphs with metric dimension β and diameter D; the maximum-order question previously had only a weak upper bound.
Method
The paper characterizes graphs in Gβ,D of order β+D and determines the exact maximum order of graphs in Gβ,D for all D and β.
Results
The paper completes the characterization of order-β+D graphs for all β≥1 and D≥3 and determines the exact maximum order for all D and β.
Takeaways & Limitations
The paper provides complete extremal characterizations at minimum order and an exact maximum-order result across the full parameter range.
Takeaways & Limitations
The twin-set argument requires |T|≥3, since the two-vertex twin-set in P3 does not preserve metric dimension after deleting one vertex.
Abstract
from arXiv · showhide
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 $\mathcal{G}_{β,D}$ be the set of graphs with metric dimension $β$ and diameter $D$. It is well-known that the minimum order of a graph in $\mathcal{G}_{β,D}$ is exactly $β+D$. The first contribution of this paper is to characterise the graphs in $\mathcal{G}_{β,D}$ with order $β+D$ for all values of $β$ and $D$. Such a characterisation was previously only known for $D\leq2$ or $β\leq1$. The second contribution is to determine the maximum order of a graph in $\mathcal{G}_{β,D}$ for all values of $D$ and $β$. Only a weak upper bound was previously known.
1. Introduction
The paper studies extremal questions for connected graphs with prescribed metric dimension β and diameter D, focusing on minimum and maximum order. It completes the minimum-order characterization for all parameters and determines the exact maximum order.
- A resolving set identifies every vertex by its vector of distances to the set, and the metric dimension is the minimum size of such a set.
- The class Gβ,D consists of connected graphs with metric dimension β and diameter D, motivating questions about their minimum and maximum order.
- The minimum order of a graph in Gβ,D is β + D.
- Earlier minimum-order characterizations covered D ≤2 or β = 1, including complete graphs when D = 1 and paths when β = 1.
- The paper characterises all graphs in Gβ,D of order β + D for β ≥1 and D ≥3, completing the characterization for every D.
- The paper determines the exact maximum order in Gβ,D for all D and β, improving on the previously known upper bound Dβ + β.
2. Graphs with Minimum Order
This section establishes the minimum possible order β + D and develops twin-graph tools to characterize exactly when a graph of diameter D satisfies β(G)=n−D.
- Minimum order: β + D is the minimum order of any graph with metric dimension β and diameter D.The lower bound follows from a diameter-realizing path, and a broom tree attains it.
- Twin vertices: A connected graph's twin vertices have identical distances to every other vertex, so every resolving set must contain at least one of them.A resolver can be exchanged between twin vertices without losing the resolving property.
- Twin vertices: For a twin-set of size at least 3, deleting any one vertex decreases the metric dimension by exactly one.More generally, deleting a subset S of size at most |T|−2 decreases the metric dimension by |S|.
- Twin graph: The twin graph preserves diameter for diameter at least 3, while its diameter is smaller precisely when it is complete.In general, diam(G*)≤diam(G), with strict inequality exactly for G*≅K_n.
- Characterization: For D≥3, β(G)=n−D holds exactly for the listed twin-graph structures: a path, two path extensions, or specified typed path cases.The characterization uses vertex types (1), (K), and (N), together with the parameter α(G*) counting non-singleton twin classes.
- Characterization: The path-extension cases require specific twin-class types: type (1N) at the added degree-3 vertex, or type (1K) on all three cycle vertices.All other vertices must be of type (1) in these two cases.
3. Graphs with Maximum Order
Section 3 determines the exact maximum order of connected graphs with diameter D and metric dimension β, proving the bound via distance-coordinate counting and constructing graphs that attain it.
- The section determines the maximum order of a graph in Gβ,D for all integers D ≥2 and β ≥1.
- The upper bound counts vertices by distance layers around a metric basis and bounds each layer using distance vectors.For vertices at distance i from a basis vertex, there are at most (2i + 1)^(β−1) possibilities; vertices outside the counted layers contribute at most (D−k)^β.
- The construction partitions coordinate vectors into regions Q and P_i,r, then defines a coordinatewise step vertex z(x,y) to connect any two vertices.The case analysis proves that z(x,y) remains in the constructed vertex set, while differing coordinates move one unit toward y.
- The vertices v1,…,vβ form a metric basis because distances from a vertex x to v_i equal its i-th coordinate.Thus the construction has metric dimension at most β; the lower-bound argument then rules out dimension below β, placing it in Gβ,D.
- The construction therefore has metric dimension exactly β and completes the proof of the maximum-order theorem.