Skip to content
DraconiticResearch
Search Sources API
186,086 studies31 sourcesUpdated 50 min ago
PreprintarXiv licencearXiv

On the structure of graphs with given odd girth and large algebraic connectivity

  • Zhengbo Chen
  • Chenxing Li
  • Zhouningxin Wang
Open at sourcePDFDOICite

Abstract

A classical result of Andrásfai, Erdős, and Sós states that every n-vertex graph with odd girth at least 2k+1 and minimum degree larger than 2n/(2k+1) is bipartite. Rather than imposing a minimum-degree condition, in this paper we investigate conditions on algebraic connectivity that force graphs of given odd girth to have a simple structure. The algebraic connectivity of a graph G, denoted by μ2(G), is the second smallest eigenvalue of its Laplacian matrix. Our main results are as follows. 1. Every n-vertex triangle-free graph G with μ2(G)≥ n/3 is bipartite. Moreover, the constant 1/3 is asymptotically best possible. 2. For k≥ 3, every n-vertex graph G of odd girth at least 2k+1 with μ2(G)>4n/(6k−1) is bipartite. 3. For k≥ 22, every n-vertex graph G of odd girth at least 2k+1 with μ2(G)>3456n/k3 is bipartite. Moreover, the term k−3 is asymptotically best possible.

Related

  1. Graphs with Minimum Algebraic Connectivity II: Regular Graphs of Even Degree
    Maryam Abdi, Ebrahim Ghorbani
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. The Algebraic Connectivity and Laplacian Spectral Radius of Token Graphs
    Xiaodi Song, Cristina Dalfó, Miquel Àngel Fiol +1
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Graphs with Minimum Algebraic Connectivity I: Proofs of Aldous-Fill and Guiduli-Mohar Conjectures
    Maryam Abdi, Ebrahim Ghorbani
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Unbalanced distance-biregular graphs with girth deficiency two
    Sebastiano Argenti, Alessandro Siciliano
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Proper conflict-free choosability of sparse graphs with girth at least seven
    Xingqin Qi, Huimin Song, Zhulou Cao
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{chen2026structure,
  title = {{On the structure of graphs with given odd girth and large algebraic connectivity}},
  author = {Zhengbo Chen and Chenxing Li and Zhouningxin Wang},
  howpublished = {arXiv},
  year = {2026},
  month = aug,
  doi = {10.48550/arxiv.2608.30799},
  eprint = {2608.30799},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.30799},
}
RIS
TY  - UNPB
TI  - On the structure of graphs with given odd girth and large algebraic connectivity
AU  - Zhengbo Chen
AU  - Chenxing Li
AU  - Zhouningxin Wang
PY  - 2026
DA  - 2026/08/31
PB  - arXiv
DO  - 10.48550/arxiv.2608.30799
UR  - https://arxiv.org/abs/2608.30799
AB  - A classical result of Andrásfai, Erdős, and Sós states that every n-vertex graph with odd girth at least 2k+1 and minimum degree larger than 2n/(2k+1) is bipartite. Rather than imposing a minimum-degree condition, in this paper we investigate conditions on algebraic connectivity that force graphs of given odd girth to have a simple structure. The algebraic connectivity of a graph G, denoted by μ_2(G), is the second smallest eigenvalue of its Laplacian matrix. Our main results are as follows. 1. Every n-vertex triangle-free graph G with μ_2(G)≥ n/3 is bipartite. Moreover, the constant 1/3 is asymptotically best possible. 2. For k≥ 3, every n-vertex graph G of odd girth at least 2k+1 with μ_2(G)>4n/(6k−1) is bipartite. 3. For k≥ 22, every n-vertex graph G of odd girth at least 2k+1 with μ_2(G)>3456n/k^3 is bipartite. Moreover, the term k^−3 is asymptotically best possible.
ER  -