Skip to content
DraconiticResearch
Search Sources API
194,067 studies31 sourcesUpdated 27 min ago
PreprintarXiv licencearXiv

Spanning tree with bounded degree sum of two adjacent vertices

  • Pham Hoang Ha
Open at sourcePDFDOICite

Abstract

In this paper, we first give a sharp sufficient condition on degree sum for a connected graph to have a spanning tree whose maximum of degree sum of two adjacent vertices are bounded. These improve some previous results on the spanning tree with bounded maximum degree. Next, we also use our main result to study the generalized rainbow connection of graphs. In particular, we give some degree sum conditions for a connected graphs to have a bounded (1,2)- rainbow connection number.

Related

  1. Local Resilience for Containment of Bounded Degree Spanning Subgraphs
    Peter Allen, Julia Böttcher, Yoshiharu Kohayakawa +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. Distinguishing adjacent vertices by ordering edges
    Aleksandra Gorzkowska, Jakub Kwaśny
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Large induced subgraphs with k vertices of maximum degree
    Zhen liu, Qinghou Zeng
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. The Erdős similarity problem for null sequences with adjacent ratios bounded below
    Kan Jiang, Lifeng Xi
    arXivPreprintarXiv licenceFull textGeometry & topologyarXiv
  5. Optimal Bounds on Spanning Tree Embeddings
    Csongor Beke, Vladimir Bošković, Nina Kamčev +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{ha2026spanning,
  title = {{Spanning tree with bounded degree sum of two adjacent vertices}},
  author = {Pham Hoang Ha},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.01020},
  eprint = {2611.01020},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.01020},
}
RIS
TY  - UNPB
TI  - Spanning tree with bounded degree sum of two adjacent vertices
AU  - Pham Hoang Ha
PY  - 2026
DA  - 2026/11/01
PB  - arXiv
DO  - 10.48550/arxiv.2611.01020
UR  - https://arxiv.org/abs/2611.01020
AB  - In this paper, we first give a sharp sufficient condition on degree sum for a connected graph to have a spanning tree whose maximum of degree sum of two adjacent vertices are bounded. These improve some previous results on the spanning tree with bounded maximum degree. Next, we also use our main result to study the generalized rainbow connection of graphs. In particular, we give some degree sum conditions for a connected graphs to have a bounded (1,2)- rainbow connection number.
ER  -