EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Chainsawing Cayley Trees: Markovian Methods in Tree Enumeration

Nubar Qocayeva

Luminis Applied Science and Engineering · 2025

DOI: 10.69760/lumin.2025000204 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Luminis Applied Science and Engineering, 2025. Verfasst von Nubar Qocayeva. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We revisit Cayley’s classical result that there are nn−2 labeled trees on nn vertices (Cayley’s formula). We introduce a stochastic pruning process on this space of Cayley trees, which we term a Markov chainsaw. In this model, edges of a labeled tree are cut or reattached randomly over time, yielding a Markov chain on the space of forests. We derive rigorous results for this process: we prove it is irreducible and aperiodic on the forest state space, and we find its stationary distribution via detailed balance. In particular, the uniform spanning-tree case recovers Cayley’s count and relates to loop-erased random walks and Wilson’s algorithm. We also implement computational experiments (in Python/NetworkX) for small nn to illustrate convergence and mixing; empirical frequencies agree with our theoretical stationary laws. Our contributions tie together classical enumeration (e.g. Prüfer codes), Markov‐chain theory (coupling and convergence), and applications in random graph processes and network reliability.

Zitieren

APA

Qocayeva, N. (2025). Chainsawing Cayley Trees: Markovian Methods in Tree Enumeration. Luminis Applied Science and Engineering. https://doi.org/10.69760/lumin.2025000204

Vancouver

Qocayeva N. Chainsawing Cayley Trees: Markovian Methods in Tree Enumeration. Luminis Applied Science and Engineering. 2025. doi:10.69760/lumin.2025000204

BibTeX
@article{Qocayeva2025,
  author = {Qocayeva, Nubar},
  title = {Chainsawing Cayley Trees: Markovian Methods in Tree Enumeration},
  journal = {Luminis Applied Science and Engineering},
  year = {2025},
  doi = {10.69760/lumin.2025000204}
}
Kostenlos starten →