Distinguishability of infinite groups and graphs

zbMATH Open1243.05086arXiv1106.4778MaRDI QIDQ426906FDOQ426906

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)

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.

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

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

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

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)

Cited In (25)

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

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)