The generalizations of Hamiltonian in oriented graphs

2024/02/06 by Jia Zhou, Zhou, Jia, Zhilan Wang +3
Computer Science · Mathematics · #05C20 #05C38 #05C70 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.2402.03878

openalex publication_date 2024/02/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

An oriented graph is an orientation of a simple graph. In 2009, Keevash, Kühn and Osthus proved that every sufficiently large oriented graph D of order n with (3n-4)/8 is Hamiltonian. Later, Kelly, Kühn and Osthus showed that it is also pancyclic. Inspired by this, we show that for any given constant t and positive integer partition n = n₁ + ⋯ + n_t, if D is an oriented graph on n vertices with minimum semidegree at least (3n-4)/8, then it contains t disjoint cycles of lengths n₁,… , n_t. Also, we determine the bounds on the semidegree of sufficiently large oriented graphs that are strongly Hamiltonian-connected, k-ordered Hamiltonian and spanning k-linked.

Related

• A Dirac type result on Hamilton cycles in oriented graphs
• Arbitrary orientations of cycles in oriented graphs
• Counting Hamilton decompositions of oriented graphs
• Counting and packing Hamilton cycles in dense graphs and oriented graphs
• Arbitrary Orientations Of Hamilton Cycles In Oriented Graphs