Bounding the Order of a Graph Using Its Diameter and Metric Dimension: A Study Through Tree Decompositions and VC Dimension
From MaRDI portal
Publication:4636778
DOI10.1137/16M1097833zbMath1384.05077arXiv1610.01475OpenAlexW2529620030WikidataQ56551544 ScholiaQ56551544MaRDI QIDQ4636778
Aline Parreau, Laurent Beaudou, Peter Dankelmann, Michael A. Henning, Arnaud Mary, Florent Foucaud
Publication date: 20 April 2018
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1610.01475
Related Items (9)
Identification of points using disks ⋮ Truncated metric dimension for finite graphs ⋮ The effect of vertex and edge deletion on the edge metric dimension of graphs ⋮ Sample Compression Schemes for Balls in Graphs ⋮ Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications ⋮ On graphs of order \(n\) with metric dimension \(n-4\) ⋮ Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds. ⋮ On the VC-dimension, covering and separating properties of the cycle and spanning tree hypergraphs of graphs ⋮ Metric dimension of maximal outerplanar graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The (weighted) metric dimension of graphs: hard and easy cases
- Identification, location-domination and metric dimension on interval and permutation graphs. I: Bounds.
- Graph minors. XX: Wagner's conjecture
- Network verification via routing table queries
- Mastermind
- On separating systems
- Discriminating codes in bipartite graphs: Bounds, extremal cardinalities, complexity
- Resolvability in graphs and the metric dimension of a graph
- Density and dimension
- Tree-decompositions with bags of small diameter
- Extremal graph theory for metric dimension and diameter
- Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
- VC-dimension and Erdős-Pósa property
- Induced subsets
- A combinatorial problem; stability and order for models and theories in infinitary languages
- On the density of families of sets
- Landmarks in graphs
- On the Complexity of Metric Dimension
- Metric Dimension of Bounded Width Graphs
- Base size, metric dimension and other invariants of groups and graphs
- Identifying Codes in Hereditary Classes of Graphs and VC-Dimension
- Graph minors. II. Algorithmic aspects of tree-width
- A characterization of some graphs with metric dimension two
- On Metric Generators of Graphs
- Graph-Theoretic Concepts in Computer Science
This page was built for publication: Bounding the Order of a Graph Using Its Diameter and Metric Dimension: A Study Through Tree Decompositions and VC Dimension
