Bounding the distinguishing number of infinite graphs and permutation groups

MaRDI QIDQ743653zbMATH OpenFDO

Authors Simon M. Smith, Mark E. Watkins

Publication date 30 September 2014

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

Full work available at URL https://arxiv.org/abs/1302.4409, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i3p40

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

infinite graphdistinguishing numberimprimitive graphdistinguishing coloringimprimitive permutation groupinfinite permutation group

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Infinite graphs (05C63) Infinite automorphism groups (20B27)

Abstract: A group of permutations G of a set V is k-distinguishable if there exists a partition of V into k parts such that only the identity permutation in G fixes setwise all of the cells of the partition. The least cardinal number k such that (G,V) is k-distinguishable is its distinguishing number. In particular, a graph X is k-distinguishable if its automorphism group Aut(X) has distinguishing number at most k in its action on the vertices of X. Various results in the literature demonstrate that when an infinite graph fails to have some property, then often some finite subgraph is similarly deficient. In this paper we show that whenever an infinite connected graph X is not k-distinguishable (for a given cardinal k), then it contains a ball B of finite radius whose distinguishing number is at least k. Moreover, this lower bound cannot be sharpened, since for any integer k greater than 3 there exists an infinite, locally finite, connected graph X that is not k-distinguishable but in which every ball of finite radius is k-distinguishable. In the second half of this paper we show that a large distinguishing number for an imprimitive graph X is traceable to a high distinguishing number either of a block of imprimitivity or of the induced action of Aut(X) on the corresponding system of imprimitivity. The distinguishing numbers of infinite primitive graphs have been examined in detail in a previous paper by the authors together with Tom W. Tucker.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 3068973 (Why is no real title available?)
• scientific article; zbMATH DE number 3087498 (Why is no real title available?)
• Distinguishability of infinite groups and graphs
• Distinguishability of locally finite trees
• Distinguishing infinite graphs
• Notes on infinite permutation groups
• Primitive Groups with no Regular Orbits on the Set of Subsets
• Symmetry breaking in graphs
• The distinguishing chromatic number
• The distinguishing number of the direct product and wreath product action.

Cited in

(9)

• scientific article; zbMATH DE number 7678748 (Why is no real title available?)
• On a theorem of Halin
• On the distinguishing number of cyclic tournaments: towards the Albertson-Collins conjecture
• On the graphs with distinguishing number equal list distinguishing number
• Distinguishability of infinite groups and graphs
• Infinite motion and 2-distinguishability of graphs and groups
• Trees with distinguishing index equal distinguishing number plus one
• The cost number and the determining number of a graph
• The distinguishing number of quasiprimitive and semiprimitive groups

This page was built for publication: Bounding the distinguishing number of infinite graphs and permutation groups

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