Skip to content
Open access

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

Aug 2026 · Electronic Journal of Combinatorics · Vol 33 · 1 citation · 46 references

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

Read PDF

Similar papers

Preprint Aug 2026

Signless Laplacian spectral conditions for rainbow matchings in a collection of bipartite graphs

Let ${\cal G}=\{G_1,\ldots,G_k\}$ be a collection of (not necessarily distinct) bipartite graphs on the same vertex bipartition $(X,Y)$, where $|X|=a$, $|Y|=b$ and $2\le k\le a\le b$. A \emph{rainbow matching} of ${\cal G}$ is a set of pairwise disjoint edges that can be chosen from distinct members of ${\cal G}$. Deno...

Zhi-Wei Guo, Nan-Xi Pan, Li Li et al. · 0 citations
Preprint Aug 2026

A sharp asymptotic bound for odd cycles in planar graphs

For graphs $G$ and $H$, let $\mathbf N(G,H)$ denote the number of unlabeled, not necessarily induced copies of $H$ in $G$, and let $\mathbf N_{\mathcal P}(n,H)$ be the maximum of $\mathbf N(G,H)$ over all $n$-vertex planar graphs $G$. We prove that, for every fixed integer $m\geq 3$, $$\mathbf N_{\mathcal P}(n,C_{2m+1}...

Zhen Liu, Chuan-Shu Wu · 0 citations
Preprint Sep 2026

A maximum matching based refinement of Brouwers conjecture

Let $G$ be a simple graph on $n$ vertices and $e(G)$ edges. Let $\mu_1\geq \cdots \geq \mu_{n-1}\geq \mu_n=0$ be the Laplacian eigenvalues of $G$. For $k=1, \ldots, n$, let $S_k(G)=\sum_{i=1}^{k}\mu_i$. Brouwers conjecture asserts that for any $k\in\{1,\ldots, n\}$, $S_k(G)\leq e(G)+\binom{k+1}{2}$. In [Bounding the su...

Tahir Shamsher · 0 citations
Preprint Sep 2026

Maximum and Minimum Spectral Radii in an Exceptional Family for Edge-Disjoint Spanning Trees

For a connected graph $G$, let $\tau(G)$ denote the maximum number of pairwise edge-disjoint spanning trees, and let $\rho(G)$ be its adjacency spectral radius. For integers $n\ge1$, $k\ge2$, and $k\le\delta\le2k-1$, let $\mathcal{G}_{n,\delta}$ be the class of connected $n$-vertex graphs with minimum degree $\delta$,...

Xuan-Yu Cao, Chun-Xiang Wang · 0 citations
Preprint Sep 2026

A proof of the maximum Laplacian energy conjecture for connected graphs via a sharp eigenvalue-sum bound

Let $S_k(G)$ denote the sum of the $k$ largest Laplacian eigenvalues of a connected graph $G$ of order $n$ and size $m$. Write $\mathrm{PA}_{n,\omega}$ for the graph obtained from an $\omega$-vertex clique by attaching $n-\omega$ pendant vertices to one of its vertices, and set \[ M_{n,k}:=\binom{k+1}{2}+n-k-1, \] the...

S. A. Mojallal · 0 citations
Preprint Oct 2026

Optimal spectral supersaturation for cliques and odd cycles

Let $Y_{n,r,q}$ be the graph obtained from the Tur\'an graph $T_{n,r}$ by adding $q$ pairwise disjoint edges inside a largest part, and let $c(n,F)$ be the minimum number of copies of $F$ created by adding a single edge to $T_{n,r}$. Fang, Li, Lin and Ma proved that for every color-critical graph $F$ with $\chi (F)=r+1...

Hongzhang Chen, Yong-Tao Li · 1 citation

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.