Distinguishability of locally finite trees
Summary: The distinguishing number \(\Delta(X)\) of a graph \(X\) is the least positive integer \(n\) for which there exists a function \(f:V(X)\rightarrow \{0,1,2,\dots,n-1\}\) such that no nonidentity element of \(\text{Aut}(X)\) fixes (setwise) every inverse image \(f^{-1}(k)\), \(k \in \{0,1,2,\dots,n-1\}\). All infinite, locally finite trees without pendant vertices are shown to be 2-distinguishable. A proof is indicated that extends 2-distinguishability to locally countable trees without pendant vertices. It is shown that every infinite, locally finite tree \(T\) with finite distinguishing number contains a finite subtree \(J\) such that \(\Delta(J)=\Delta(T)\). Analogous results are obtained for the distinguishing chromatic number, namely the least positive integer \(n\) such that the function \(f\) is also a proper vertex-coloring.
- On the local distinguishing numbers of cycles
- Extending precolorings to distinguish group actions
- List distinguishing parameters of trees
- On the distinguishing number of cyclic tournaments: towards the Albertson-Collins conjecture
- The cost of 2-distinguishing hypercubes
- Trees with distinguishing index equal distinguishing number plus one
- Asymmetrizing trees of maximum valence \(2^{\aleph_0}\)
- Infinite motion and 2-distinguishability of graphs and groups
- The distinguishing index of infinite graphs
- Distinguishing graphs with intermediate growth
- Breaking graph symmetries by edge colourings
- Local greatest equivalence classes of -trees
- Nordhaus-Gaddum theorem for the distinguishing chromatic number
- Endomorphism breaking in graphs
- Distinguishing trees in linear time
- scientific article; zbMATH DE number 1472093 (Why is no real title available?)
- Paint cost and the frugal distinguishing number
- Distinguishing generalized Mycielskian graphs
- A counterexample to the reconstruction conjecture for locally finite trees
- scientific article; zbMATH DE number 7678748 (Why is no real title available?)
- Automorphisms of restricted parabolic trees and Sylow p-subgroups of the finitary symmetric group
- Distinguishing orthogonality graphs
- On asymmetric colourings of graphs with bounded degrees and infinite motion
- Bounding the distinguishing number of infinite graphs and permutation groups
- On computing the distinguishing numbers of trees and forests
- Local finiteness, distinguishing numbers, and Tucker's conjecture
- The distinguishing chromatic number of Cartesian products of two complete graphs
This page was built for publication: Distinguishability of locally finite trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q874003)
