EUVIMEDEUVIMED entdecken
Crossref

Cubic bipartite graphs with minimum spectral gap

Ruifang Liu, Jie Xue

Advances in Applied Mathematics · 2026-10 · 180 · 103134

DOI: 10.1016/j.aam.2026.103134 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Advances in Applied Mathematics, 2026-10. Verfasst von Ruifang Liu und 1 weiteren Autor:innen. Die Arbeit nennt 29 Literaturangaben. Gefördert von: Henan Provincial Education Development Foundation, National Natural Science Foundation of China.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The difference between the two largest eigenvalues of the adjacency matrix of a graph $G$ is called the spectral gap of $G.$ If $G$ is a regular graph, then its spectral gap is equal to algebraic connectivity. Abdi, Ghorbani and Imrich, in [European J. Combin. 95 (2021) 103328], showed that the minimum algebraic connectivity of cubic connected graphs on $2n$ vertices is $(1+o(1))\frac{\pi^{2}}{2n^{2}}$, which is attained on non-bipartite graphs. Motivated by the above result, we in this paper investigate the algebraic connectivity of cubic bipartite graphs. We prove that the minimum algebraic connectivity of cubic bipartite graphs on $2n$ vertices is $(1+o(1))\frac{\pi^{2}}{n^{2}}$. Moreover, the unique cubic bipartite graph with minimum algebraic connectivity is completed characterized. Based on the relation between the algebraic connectivity and spectral gap of regular graphs, the cubic bipartite graph with minimum spectral gap and the corresponding asymptotic value are also presented. In [J. Graph Theory 99 (2022) 671--690], Horak and Kim established a sharp upper bound for the number of perfect matchings in terms of the Fibonacci number. We obtain a spectral characterization for the extremal graphs by showing that a cubic bipartite graph has the maximum number of perfect matchings if and only if it minimizes the algebraic connectivity.

Förderung

  • Henan Provincial Education Development Foundation
  • National Natural Science Foundation of China

Zitieren

APA

Liu, R., & Xue, J. (2026). Cubic bipartite graphs with minimum spectral gap. Advances in Applied Mathematics, 180, 103134. https://doi.org/10.1016/j.aam.2026.103134

Vancouver

Liu R, Xue J. Cubic bipartite graphs with minimum spectral gap. Advances in Applied Mathematics. 2026;180:103134. doi:10.1016/j.aam.2026.103134

BibTeX
@article{Liu2026,
  author = {Liu, Ruifang and Xue, Jie},
  title = {Cubic bipartite graphs with minimum spectral gap},
  journal = {Advances in Applied Mathematics},
  year = {2026},
  volume = {180},
  pages = {103134},
  doi = {10.1016/j.aam.2026.103134}
}
Kostenlos starten →