Distinguishing density and the distinct spheres condition

DOI10.1016/J.EJC.2020.103139MaRDI QIDQ2198972zbMATH OpenOpenAlexFDO

Authors Wilfried Imrich, Florian Lehner, Simon M. Smith

Publication date 15 September 2020

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

2-distinguishing cost\(n\)-distinguishing coloringinfinite motion conjecture

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62) Infinite graphs (05C63)

Abstract: If a graph $G$ has distinguishing number 2, then there exists a partition of its vertex set into two parts, such that no nontrivial automorphism of $G$ fixes setwise the two parts. Such a partition is called a 2-distinguishing coloring of $G$, and the parts are called its color classes. If $G$ admits such a coloring, it is often possible to find another in which one of the color classes is sparse in a certain sense. In this case we say that $G$ has 2-distinguishing density zero. An extreme example of this would be an infinite graph admitting a 2-distinguishing coloring in which one of the color classes is finite. If a graph $G$ contains a vertex $v$ such that, for all $ninmathbbN$, any two distinct vertices equidistant from $v$ have nonequal $n$-spheres, then we say that $G$ satisfies the Distinct Spheres Condition. In this paper we prove a general result: any countable connected graph that satisfies the Distinct Spheres Condition is 2-distinguishable with density zero. We present two proofs of this, one that uses a deterministic coloring, and another (that applies only to locally finite graphs) using a random coloring. From this result, we deduce that several important families of countably infinite and connected graphs are 2-distinguishable with density zero, including those that are locally finite and primitive. Furthermore, we prove that any connected graph with infinite motion and subquadratic growth is 2-distinguishable with density zero.

Recommendations

• Distinguishing graphs with infinite motion and nonlinear growth
• Distinguishing graphs with intermediate growth
• Bounds for distinguishing invariants of infinite graphs
• Distinguishing infinite graphs with bounded degrees
• Infinite motion and 2-distinguishability of graphs and groups

Cites work

• Base size, metric dimension and other invariants of groups and graphs
• Chains of subgroups in symmetric groups
• Distinguishability of infinite groups and graphs
• Distinguishing graphs with infinite motion and nonlinear growth
• Distinguishing graphs with intermediate growth
• Handbook of product graphs
• Infinite graphs with finite 2-distinguishing cost
• Infinite motion and 2-distinguishability of graphs and groups
• Primitive Groups with no Regular Orbits on the Set of Subsets
• Random colourings and automorphism breaking in locally finite graphs

Cited in

(3)

• Distinguishing graphs with infinite motion and nonlinear growth
• Coarse distinguishability of graphs with symmetric growth
• Finite and infinite vertex-transitive cubic graphs and their distinguishing cost and density

This page was built for publication: Distinguishing density and the distinct spheres condition

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