Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 15 min ago
PreprintarXiv licencearXiv

Connected graphs with equal independence number and radius

  • Xingzhi Zhan
Open at sourcePDFDOICite

Abstract

A classical theorem states that the independence number of any connected graph is at least its radius. In 2007, DeLaViña, Pepper, and Waller proved that every connected graph with equal independence number and radius is traceable. We first give a new short proof of this theorem and then prove two results for graphs of higher connectivity. (1) Every 2-connected graph with equal independence number and radius is Hamiltonian. (2) Every 3-connected graph with equal independence number and radius is Hamiltonian-connected and pancyclic. Several lemmas used in the proofs are of independent interest.

Related

  1. Independence number, essential connectivity and the distance spectral radius of graphs
    Shuang Ding, Dan Li, Yuanyuan Chen
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. The maximum spectral radius of connected graphs with prescribed order and size
    Dragan Stevanović
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Tree-independence number VIII. 3PC-free graphs have logarithmic tree-independence number
    Maria Chudnovsky, Julien Codsi, Ajaykrishnan E S +2
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Strong complete immersions in graphs with independence number two
    Zijian Deng, Chuanshu Wu
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Connected graphs having maximum signless Laplacian spectral radius
    Di-Jian Wang, Hong-Yan Ge, Shi-Cai Gong +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{zhan2026connected,
  title = {{Connected graphs with equal independence number and radius}},
  author = {Xingzhi Zhan},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.30165},
  eprint = {2610.30165},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.30165},
}
RIS
TY  - UNPB
TI  - Connected graphs with equal independence number and radius
AU  - Xingzhi Zhan
PY  - 2026
DA  - 2026/10/14
PB  - arXiv
DO  - 10.48550/arxiv.2610.30165
UR  - https://arxiv.org/abs/2610.30165
AB  - A classical theorem states that the independence number of any connected graph is at least its radius. In 2007, DeLaViña, Pepper, and Waller proved that every connected graph with equal independence number and radius is traceable. We first give a new short proof of this theorem and then prove two results for graphs of higher connectivity. (1) Every 2-connected graph with equal independence number and radius is Hamiltonian. (2) Every 3-connected graph with equal independence number and radius is Hamiltonian-connected and pancyclic. Several lemmas used in the proofs are of independent interest.
ER  -