Spectral Radius, Transversal Hamilton Paths and Cycles in Bipartite Graph Families
The Electronic Journal of Combinatorics · 07.08.2026 · 33 (3)
DOI: 10.37236/14520 ↗Kurz gefasst
Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 07.08.2026. Verfasst von Xiaocong He und 1 weiteren Autor:innen.
Abstract (Originalsprache)
A theorem of Li and Ning [Linear Algebra Appl. 515 (2017)] states that, for $n\geq4$, every balanced bipartite graph $G$ on $2n$ vertices with spectral radius $\lambda(G)\geq\sqrt{n(n-1)}$ contains a Hamilton path unless $G\simeq K_{n,n-1}\cup K_1$. Let $[n]=\{1,2,\ldots,n\}$. We prove a generalization of this theorem in the setting of graph transversals. Namely, for $n\geq4$, we show that given a family $\mathcal{G}=\{G_1,G_2,\ldots,G_{2n-1}\}$ of $2n-1$ bipartite graphs on a common set $V$ of $2n$ vertices with a common balanced bipartition, if $\lambda(G_i)\geq\sqrt{n(n-1)}$ for every $i\in [2n-1]$, then there exists a transversal Hamilton path on $V$ unless $G_1=G_2=\cdots=G_{2n-1}$ and $G_1\simeq K_{n,n-1}\cup K_1$. We also show spectral analogue of transversal Hamilton cycle in bipartite graph families. Let $B_n^1$ be the graph obtained from $K_{n,n}$ by deleting all edges in its one subgraph $K_{n-1,1}$. Given a family $\mathcal{G}=\{G_1,G_2,\ldots,G_{2n}\}$ of $2n$ bipartite graphs on a common set $V$ of $2n$ vertices with a common balanced bipartition, for $n\geq4$, we prove that if $\lambda(G_i)\geq\lambda(B_n^1)$ for every $i\in [2n]$, then $\mathcal{G}$ contains a transversal Hamilton cycle, unless $G_1=G_2=\cdots=G_{2n}$ and $G_1\simeq B_n^1$. Our result extends a result of Li and Ning [Linear Multilinear Algebra 64 (11) (2016)].
Zitieren
APA
He, X., & Lu, R. (2026). Spectral Radius, Transversal Hamilton Paths and Cycles in Bipartite Graph Families. The Electronic Journal of Combinatorics, 33(3). https://doi.org/10.37236/14520
Vancouver
He X, Lu R. Spectral Radius, Transversal Hamilton Paths and Cycles in Bipartite Graph Families. The Electronic Journal of Combinatorics. 2026;33(3). doi:10.37236/14520
BibTeX
@article{He2026,
author = {He, Xiaocong and Lu, Rongrong},
title = {Spectral Radius, Transversal Hamilton Paths and Cycles in Bipartite Graph Families},
journal = {The Electronic Journal of Combinatorics},
year = {2026},
volume = {33},
number = {3},
doi = {10.37236/14520}
}
EUVIMED