Skip to content
DraconiticResearch
Search Sources API
182,460 studies31 sourcesUpdated 34 min ago
PreprintCC BY 4.0arXiv

Balanced Spanning Trees for Triangular Strip Lattices

  • Saugat Dhakal
  • Long Nguyen
  • Yandi Wu
Open at sourcePDFDOICite

Abstract

A balanced spanning tree is a spanning tree that contains an edge whose removal partitions the vertices into exactly two connected subtrees of equal size. In this paper, we establish explicit recurrence relations for the number of spanning trees in 2 × n triangular strip lattices- obtained by adding a diagonal edge to each square of a 2 × n grid graph- generalizing combinatorial counting techniques introduced by Raff [Raf08]. We then adapt arguments of Gallagher and Tapp [GT25] to count balanced spanning trees of arbitrary triangular strip lattices. We establish sharp asymptotic bounds for the proportion of balanced spanning trees as n → ∞. Finally, we determine the probability that a spanning tree of a 2 × n triangular strip lattice chosen uniformly at random is balanced as n → ∞.

Related

  1. Note on near-spanning balanced antidirected trees missing from regular tournaments
    Gregory Gutin, Yiming Hao
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Spectral radius and edge-disjoint spanning trees of graphs with edge connectivity
    Jia Wei, Muhuo Liu, Zhifu You +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. A quadratic ancestor inequality for spanning trees
    Gefei Cai
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsMathematical physicsarXiv
  4. Spanning k-trees and the colorful Carathéodory theorem
    Mikhail Bludov, Alexander Polyanskii
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. On Hypergraph Colorings and Completely Independent Spanning Trees in Chordal Graphs
    Mohammed Lalou, Nader Mbarek, Abdallah Skender +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{dhakal2026balanced,
  title = {{Balanced Spanning Trees for Triangular Strip Lattices}},
  author = {Saugat Dhakal and Long Nguyen and Yandi Wu},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.08222},
  eprint = {2609.08222},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.08222},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Balanced Spanning Trees for Triangular Strip Lattices
AU  - Saugat Dhakal
AU  - Long Nguyen
AU  - Yandi Wu
PY  - 2026
DA  - 2026/09/08
PB  - arXiv
DO  - 10.48550/arxiv.2609.08222
UR  - https://arxiv.org/abs/2609.08222
AB  - A balanced spanning tree is a spanning tree that contains an edge whose removal partitions the vertices into exactly two connected subtrees of equal size. In this paper, we establish explicit recurrence relations for the number of spanning trees in 2 × n triangular strip lattices- obtained by adding a diagonal edge to each square of a 2 × n grid graph- generalizing combinatorial counting techniques introduced by Raff [Raf08]. We then adapt arguments of Gallagher and Tapp [GT25] to count balanced spanning trees of arbitrary triangular strip lattices. We establish sharp asymptotic bounds for the proportion of balanced spanning trees as n → ∞. Finally, we determine the probability that a spanning tree of a 2 × n triangular strip lattice chosen uniformly at random is balanced as n → ∞.
ER  -