Characterization of 2-distinguishable trees by branch orbit counts

Let TT be a tree. For a vertex ww and a neighbor xx of ww, let TxT^x denote the component containing xx after deleting ww, let μ(x)\mu(x) denote the number of isomorphism types among the branches rooted at xx, and let a(Tx)a(T^x) denote the number of distinguishing subsets of TxT^x. Characterization conjecture. The tree TT is 22-distinguishable if and only if, for any vertex ww and any neighbor xx of ww, μ(x)a(Tx)\mu(x)\leq a(T^x) if TxT^x is finite, and

μ(x)=2Tx\mu(x)=2^{|T^x|}

if TxT^x is infinite. This would characterize 2-distinguishable trees in terms of the number of branch types and distinguishing subsets of their rooted components, extending the preceding characterization of aa-maximum trees; the paper provides no resolution of the conjecture.

Sources & referencesView supporting material

Primary source

Wilfried Imrich, Rafał Kalinowski, Florian Lehner, Monika Pilśniak and Marcin Stawiski, “Distinguishing finite and infinite trees of arbitrary cardinality”, arXiv:2506.14402 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.