Distinguishability of infinite groups and graphs

MaRDI QIDQ426906zbMATH OpenFDO

Authors Simon M. Smith, Thomas W. Tucker, Mark E. Watkins

Publication date 12 June 2012

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

Full work available at URL https://arxiv.org/abs/1106.4778, http://www.emis.de/journals/EJC/ojs/index.php/eljc/article/view/v19i2p27

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

zbMATH Keywords

primitive permutation groupCartesian product of graphsdistinguishing numberdistinct spheres conditioninfinite motionprimitive graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Enumeration in graph theory (05C30) Infinite graphs (05C63) Graph operations (line graphs, products, etc.) (05C76) Primitive groups (20B15) Infinite automorphism groups (20B27)

Abstract: The {em distinguishing number} of a group $G$ acting faithfully on a set $V$ is the least number of colors needed to color the elements of $V$ so that no non-identity element of the group preserves the coloring. The {em distinguishing number} of a graph is the distinguishing number of its full automorphism group acting on its vertex set. A connected graph $Gamma$ is said to have {em connectivity 1} if there exists a vertex $alphainVGamma$ such that $Gammasetminusalpha$ is not connected. For $alphainV$, an orbit of the point stabilizer $G_{a}lpha$ is called a {em suborbit} of $G$. We prove that every connected primitive graph with infinite diameter and countably many vertices has distinguishing number 2. Consequently, any infinite, connected, primitive, locally finite graph is 2-distinguishable; so, too, is any infinite primitive group with finite suborbits. We also show that all denumerable vertex-transitive graphs of connectivity 1 and all Cartesian products of connected denumerable graphs of infinite diameter have distinguishing number 2. All of our results follow directly from a versatile lemma which we call The Distinct Spheres Lemma.

Recommendations

• Bounding the distinguishing number of infinite graphs and permutation groups
• On primitive permutation groups with nontrivial global stabilizers.
• Distinguishing infinite graphs
• Distinguishing numbers for graphs and groups
• Infinite motion and 2-distinguishability of graphs and groups

Cited in

(25)

• Orbit-equivalent infinite permutation groups.
• Distinguishing generalized Mycielskian graphs
• Local finiteness, distinguishing numbers, and Tucker's conjecture
• Distinguishing infinite graphs
• The cost of 2-distinguishing hypercubes
• scientific article; zbMATH DE number 7678748 (Why is no real title available?)
• Paint cost and the frugal distinguishing number
• Distinguishing density and the distinct spheres condition
• Endomorphism breaking in graphs
• A note on computable distinguishing colorings
• Distinguishing number of countable homogeneous relational structures
• Bounding the distinguishing number of infinite graphs and permutation groups
• Reconstructing a minimal topological dynamical system from a set of return times
• Symmetry parameters for Mycielskian graphs
• Infinite motion and 2-distinguishability of graphs and groups
• Finite and infinite vertex-transitive cubic graphs and their distinguishing cost and density
• Distinguishability of a Semi-Group by a Machine
• Distinguishing orthogonality graphs
• Distinguishing graphs by edge-colourings
• The distinguishing number of quasiprimitive and semiprimitive groups
• Distinguishing Cartesian products of countable graphs
• The distinguishing index of infinite graphs
• Breaking graph symmetries by edge colourings
• Distinguishing graphs with intermediate growth
• Distinguishing graphs of maximum valence 3

This page was built for publication: Distinguishability of infinite groups and graphs

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