On a theorem of Halin

DOI10.1007/S12188-016-0167-9MaRDI QIDQ1688265zbMATH OpenOpenAlexFDO

Authors Wilfried Imrich, Simon M. Smith

Publication date 5 January 2018

Published in Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.04395, http://eprints.lincoln.ac.uk/id/eprint/26752/1/Imrich%20Smith%20On%20a%20theorem%20of%20Halin-Published-Version.pdf

zbMATH Keywords

automorphismdistinguishing numberinfinite graph

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Infinite graphs (05C63)

Abstract: This note presents a new, elementary proof of a generalization of a theorem of Halin to graphs with unbounded degrees, which is then applied to show that every connected, countably infinite graph G with a subdegree-finite, infinite automorphism group whose cardinality is strictly less than continuum, has a finite set F of vertices that is setwise stabilized only by the identity automorphism. A bound on the size of such sets, which are called distinguishing, is also provided. To put this theorem of Halin and its generalization into perspective, we also discuss several related non-elementary, independent results and their methods of proof.

Review text

The main result of this work is the following. If \(G\) is a graph with countably many vertices, then \(\text{Aut}(G)\) is countable or has cardinality \(2^{\aleph_0}\). Moreover, \(\text{Aut}(G)\) is countable if and only if \(\text{Aut}(G)\) has a finite base. This is, on one side, a generalization of a result from [\textit{R. Halin}, Abh. Math. Semin. Univ. Hamb. 39, 251--283 (1973; Zbl 0265.05118)] and, on the other hand, it presents a graph theoretical proof of the mentioned result, which was known even before Halin's paper in the different areas of mathematics (infinitary languages and mathematical logic). As a side effect a new bound on distinguishing number is presented as well.

Recommendations

• A note on graphs with countable automorphism group
• Distinguishing infinite graphs with bounded degrees
• Bounding the distinguishing number of infinite graphs and permutation groups
• Distinguishing infinite graphs
• Distinguishing graphs with infinite motion and nonlinear growth

Cites work

• A note on automorphism groups of countably infinite structures
• Asymmetric trees with two prescribed degrees
• Automorphisms and endomorphisms of infinite locally finite graphs
• Chains of subgroups in symmetric groups
• scientific article; zbMATH DE number 44603 (Why is no real title available?)
• scientific article; zbMATH DE number 3372013 (Why is no real title available?)
• Infinite graphs with finite 2-distinguishing cost
• Local definability theory
• Small label classes in 2-distinguishing labelings
• Subgroups of small Index in infinite Symmetric Groups
• Symmetry breaking in graphs

Cited in

(5)

• Remarks on an elementary proof of Halász's theorem
• On a theorem of Helly
• scientific article; zbMATH DE number 4005283 (Why is no real title available?)
• scientific article; zbMATH DE number 96088 (Why is no real title available?)
• scientific article; zbMATH DE number 7678748 (Why is no real title available?)

This page was built for publication: On a theorem of Halin

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