Article in press
Authors:
Title:
Hamiltonian cycles through a linear forest in bipartite graphs
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2024-09-15 , Revised: 2025-04-27 , Accepted: 2025-04-27 , Available online: 2025-05-29 , https://doi.org/10.7151/dmgt.2588
Abstract:
A graph is a linear forest if every component is a nontrivial path. Let $G$ be
a balanced bipartite graph with $n$ vertices. Let $F$ be a set of $m$ edges of
$G$ that induces a linear forest. Zamani and West provided a sufficient
condition for $G$ to contain the linear forest in a Hamiltonian cycle, as
presented in [Spanning cycles through specified edges in bipartite graphs,
J. Graph Theory 71 (2012) 1–17]. The proof presented in this paper
establishes the existence of Hamiltonian cycles $C_{i}$ such that $|E(C_{i})
\cap F|=i$ $(0\leqslant i \leqslant m)$ in $G$ if any two nonadjacent vertices
in opposite partite sets have degree-sum at least $n/2+m+1$.
Keywords:
Hamiltonian cycle, bipartite graph, linear forest
References:
- B. Bollobás and G. Brightwell, Cycles through specified vertices, Combinatorica 13 (1993) 147–155.
https://doi.org/10.1007/BF01303200 - J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Elsevier, MacMillan, New York, London, 1976).
- L. Pósa, On the circuits of finite graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl. 8 (1963) 355–361.
- L. Stacho, Locally pancyclic graphs, J. Combin. Theory Ser. B 76 (1999) 22–40.
https://doi.org/10.1006/jctb.1998.1885 - T. Sugiyama, Hamiltonian cycles through a linear forest, SUT J. Math. 40 (2004) 103–109.
https://doi.org/10.55937/sut/1108749122 - M. Las Vergnas, Problèmes de couplages et problèmes Hamiltoniens en théorie des graphes, Ph.D. Thesis (University of Paris, 1972).
- O. Ore, A note on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55.
https://doi.org/10.2307/2308928 - R. Zamani, and D.B. West, Spanning cycles through specified edges in bipartite graphs, J. Graph Theory 71 (2012) 1–17.
https://doi.org/10.1002/jgt.20627
Close