EUVIMEDEUVIMED entdecken
Crossref

Spectral Radius, Transversal Hamilton Paths and Cycles in Bipartite Graph Families

Xiaocong He, Rongrong Lu

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →