On the metric dimension of Cartesian powers of a graph

DOI10.1016/J.JCTA.2019.01.002MaRDI QIDQ2424901zbMATH OpenOpenAlexFDO

Authors Zilin Jiang, Nikita Polyanskii

Publication date 25 June 2019

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

Cartesian productmetric dimensionMöbius functionresolving set

Mathematics Subject Classification ID

Distance in graphs (05C12) Connectivity (05C40) Graph operations (line graphs, products, etc.) (05C76)

Abstract: A set of vertices $S$ resolves a graph if every vertex is uniquely determined by its vector of distances to the vertices in $S$. The metric dimension of a graph is the minimum cardinality of a resolving set of the graph. Fix a connected graph $G$ on $qge2$ vertices, and let $M$ be the distance matrix of $G$. We prove that if there exists $winmathbb{Z}^q$ such that $su{m}_i{w}_i=0$ and the vector $Mw$, after sorting its coordinates, is an arithmetic progression with nonzero common difference, then the metric dimension of the Cartesian product of $n$ copies of $G$ is $(2+o(1))n/lo{g}_{q}n$. In the special case that $G$ is a complete graph, our results close the gap between the lower bound attributed to ErdH{o}s and R'enyi and the upper bounds developed subsequently by Lindstr"om, Chv'atal, Kabatianski, Lebedev and Thorpe.

Recommendations

• On the metric dimension of Cartesian products of graphs
• On the Metric Dimension of Cartesian Products of Graphs
• The metric dimension of Cartesian products of graphs
• The metric dimensions of a complete \(n\)-partite graph and its Cartesian product with a path
• On the metric dimension of infinite graphs

Cites work

• A Combinatory Detection Problem
• An information-theoretic method in combinatorial theory
• Determinants on Semilattices
• Determination of a Subset from Certain Combinatorial Properties
• scientific article; zbMATH DE number 3494441 (Why is no real title available?)
• scientific article; zbMATH DE number 3499765 (Why is no real title available?)
• scientific article; zbMATH DE number 3544092 (Why is no real title available?)
• scientific article; zbMATH DE number 3559318 (Why is no real title available?)
• scientific article; zbMATH DE number 1332564 (Why is no real title available?)
• scientific article; zbMATH DE number 3248638 (Why is no real title available?)
• scientific article; zbMATH DE number 3194843 (Why is no real title available?)
• scientific article; zbMATH DE number 3080144 (Why is no real title available?)
• Mastermind
• On a Combinatorial Problem in Number Theory
• On a problem in additive number theory
• On metric dimension of nonbinary Hamming spaces
• On Metric Generators of Graphs
• On Möbius Functions and a Problem in Combinatorial Number Theory
• On the Metric Dimension of Cartesian Products of Graphs

Cited in

(37)

• Maker-breaker resolving game
• A bridge between the minimal doubly resolving set problem in (folded) hypercubes and the coin weighing problem
• Solving static permutation mastermind using \(O(n \log n)\) queries
• Local metric dimension for graphs with small clique numbers
• The doubly metric dimension of cylinder graphs and torus graphs
• Completeness-resolvable graphs
• On vertices contained in all or in no metric basis
• Resolving sets tolerant to failures in three-dimensional grids
• The effect of vertex and edge deletion on the edge metric dimension of graphs
• Metric dimension, minimal doubly resolving sets, and the strong metric dimension for jellyfish graph and cocktail party graph
• On the metric dimension of the folded \(n\)-cube
• Strong resolving graph of a zero-divisor graph
• Levenshtein graphs: resolvability, automorphisms \& determining sets
• Mixed metric dimension of some graphs
• The metric dimension and metric independence of a graph
• On the Strong Metric Dimension of Cartesian Sum Graphs
• On the Metric Dimension of Cartesian Products of Graphs
• The metric dimensions of a complete \(n\)-partite graph and its Cartesian product with a path
• On the metric dimension of Cartesian products of graphs
• The metric dimension of Cartesian products of graphs
• scientific article; zbMATH DE number 969975 (Why is no real title available?)
• On metric dimensions of hypercubes
• Metric dimension of complement of annihilator graphs associated with commutative rings
• Computing the strong metric dimension for co-maximal ideal graphs of commutative rings
• Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications
• Optimal schemes for combinatorial query problems with integer feedback
• Resolvability and convexity properties in the Sierpiński product of graphs
• Locating Number of Biswapped Networks
• Nonoverlapping convex polytopes with vertices in a Boolean cube and other problems in coding theory
• Metric Dimension of a Diagonal Family of Generalized Hamming Graphs
• The doubly metric dimensions of cactus graphs and block graphs
• Metric dimension of the complement of the zero-divisor graph
• The edge metric dimensions of convex polytopes
• Metric dimension in a prime ideal sum graph of a commutative ring
• Fault-tolerant metric dimension of some plane graphs
• The nonlocal metric dimension of some convex polytopes
• Cartesian powers of graphs can be distinguished by two labels

This page was built for publication: On the metric dimension of Cartesian powers of a graph

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