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

Abstract

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)].