Skip to content
DraconiticResearch
Search Sources API
182,544 studies31 sourcesUpdated 25 min ago
PreprintarXiv licencearXiv

Maximum number of spanning trees in bipartite graphs with a given diameter

  • Shaohan Xu
  • Ivan Damnjanović
  • Kexiang Xu
Open at sourcePDFDOICite

Abstract

The number of spanning trees is a classical graph invariant and an important measure of network reliability, as it counts the minimal connected spanning substructures that can maintain communication in a network. Let ℬ(n,d) be the set of connected bipartite graphs of order n and diameter d. Motivated by reliability design problems for bipartite network models with fixed order and diameter, this paper determines all graphs with the maximum number of spanning trees in ℬ(n,d). The result gives an extremal characterization of bipartite network topologies with the largest number of connected spanning backbones under prescribed order and diameter constraints, and provides a structural reference for the design of reliable bipartite networks.

Related

  1. Wild number for spanning trees in complete and complete bipartite graphs
    Aleyah Dawkins, Alexander Nappo, Jessie Tong +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. The asymptotic maximum oriented diameter of graphs
    Jiangdong Ai, Yaokun Feng, Hui Lei +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. A sharp upper bound on the number of spanning forests of regular graphs
    T. Wu, S. Lu, X. Dong
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Maximum Edge Open Packing on AT-Free, Chordal, and Convex Bipartite Graphs
    Gautam K. Das, Kamal Santra
    arXivPreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. A Turán-type extremal problem for the number of spanning trees in C4-free graphs
    Shaohan Xu, Fengming Dong, Kexiang Xu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{xu2026maximum,
  title = {{Maximum number of spanning trees in bipartite graphs with a given diameter}},
  author = {Shaohan Xu and Ivan Damnjanović and Kexiang Xu},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.15502},
  eprint = {2609.15502},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.15502},
}
RIS
TY  - UNPB
TI  - Maximum number of spanning trees in bipartite graphs with a given diameter
AU  - Shaohan Xu
AU  - Ivan Damnjanović
AU  - Kexiang Xu
PY  - 2026
DA  - 2026/09/14
PB  - arXiv
DO  - 10.48550/arxiv.2609.15502
UR  - https://arxiv.org/abs/2609.15502
AB  - The number of spanning trees is a classical graph invariant and an important measure of network reliability, as it counts the minimal connected spanning substructures that can maintain communication in a network. Let ℬ(n,d) be the set of connected bipartite graphs of order n and diameter d. Motivated by reliability design problems for bipartite network models with fixed order and diameter, this paper determines all graphs with the maximum number of spanning trees in ℬ(n,d). The result gives an extremal characterization of bipartite network topologies with the largest number of connected spanning backbones under prescribed order and diameter constraints, and provides a structural reference for the design of reliable bipartite networks.
ER  -