Transversal and Hamiltonicity in a bipartite graph collection

Read full text
Authors: Menghan Ma, Lihua You, Xiaoxue Zhang
Cited by: 0

Abstract

Let $\mathbf{G}=\{G_1,\dots,G_{s}\}$ be a collection of $s$ bipartite graphs with the same bipartition $V=(X,Y)$. For a path $P$ with $V(P)=V$ and $|E(P)|=s$, if there exists an injection $ϕ$: $E(P)\rightarrow [s]$ such that $e\in E(G_{ϕ(e)})$ for each $e\in E(P)$, then we say that the Hamiltonian path $P$ is a $\mathbf{G}$-transversal. A bipartite graph collection $\mathbf{G}$ is called Hamiltonian connected if for any two vertices $x\in X$ and $y\in Y$, there exists a $\mathbf{G}$-transversal isomorphic to a Hamiltonian path between $x$ and $y$. In this paper, we give the minimum degree conditions that ensure the existence of a $\mathbf{G}$-transversal isomorphic to a Hamiltonian path and the Hamiltonian connectivity of a balanced bipartite graph collection $\mathbf{G}$, which improve the results of [Hu, Li, Li and Xu, Discrete Math., 2024]. Moreover, we also provide a minimum degree condition that guarantees a nearly balanced bipartite graph collection $\mathbf{G}$ contains a $\mathbf{G}$-transversal isomorphic to a Hamiltonian path.

Fields of Study & Subjects

Limits and Structures in Graph Theory Advanced Graph Theory Research Advanced Combinatorial Mathematics

Publication details

Journal / source
arXiv (Cornell University)
Publication date
25 January 2026
Document type
Preprint