DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2024): 0.8

5-year Journal Impact Factor (2024): 0.7

CiteScore (2024): 2.1

SNIP (2024): 1.162

Discussiones Mathematicae Graph Theory

Article in press


Authors:

X. Li

Xia Li

Department of Mathematics, Taiyuan University of Technology, Taiyuan 030024, China

email: 15525142916@163.com

0000-0001-7584-6877

Y. Li
W. Yang

Weihua Yang

Department of Mathematics, Taiyuan University of Technology, Shanxi Taiyuan-030024

email: yangweihua@tyut.edu.cn

0000-0002-3827-7334

Title:

Hamiltonian cycles through a linear forest in bipartite graphs

PDF

Source:

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:

  1. B. Bollobás and G. Brightwell, Cycles through specified vertices, Combinatorica 13 (1993) 147–155.
    https://doi.org/10.1007/BF01303200
  2. J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Elsevier, MacMillan, New York, London, 1976).
  3. L. Pósa, On the circuits of finite graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl. 8 (1963) 355–361.
  4. L. Stacho, Locally pancyclic graphs, J. Combin. Theory Ser. B 76 (1999) 22–40.
    https://doi.org/10.1006/jctb.1998.1885
  5. T. Sugiyama, Hamiltonian cycles through a linear forest, SUT J. Math. 40 (2004) 103–109.
    https://doi.org/10.55937/sut/1108749122
  6. M. Las Vergnas, Problèmes de couplages et problèmes Hamiltoniens en théorie des graphes, Ph.D. Thesis (University of Paris, 1972).
  7. O. Ore, A note on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55.
    https://doi.org/10.2307/2308928
  8. 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