• Chỉ mục bởi
  • Năm xuất bản

On vertex disjoint cycles of different lengths in 3-regular digraphs

Tan N.D. Institute of Mathematics, Vietnam Academy of Science and Technology, 18 Hoang Quoc Viet RoadHanoi 10307, Viet Nam|

Discrete Mathematics Số 12, năm 2015 (Tập 338, trang 2485-2491)

ISSN: 0012365X

ISSN: 0012365X

DOI: 10.1016/j.disc.2015.06.016

Tài liệu thuộc danh mục: Scopus



Tóm tắt tiếng anh
Abstract Henning and Yeo (2012) conjectured that a 3-regular digraph D contains two vertex disjoint directed cycles of different lengths if either D is of sufficiently large order or D is bipartite. In this paper, we disprove the first conjecture. Further, we give support for the second conjecture by proving that every bipartite 3-regular digraph, which either possesses a cycle factor with at least two directed cycles or has a Hamilton cycle C=v0,v1,...,vn-1,v0 and a spanning 1-circular subdigraph D(n,S), where S={s} with s>1 and the orderings of the vertices in D(n,S) and in the Hamilton cycle C are the same, does indeed have two vertex disjoint directed cycles of different lengths. © 2015 Elsevier B.V.

Xem chi tiết