Powers of Hamiltonian cycles in randomly augmented graphs

We study the existence of powers of Hamiltonian cycles in graphs with large minimum degree to which some additional edges have been added in a random manner. It follows from the theorems of Dirac and of Komlós, Sarközy, and Szemerédi that for every k ≥ 1 and sufficiently large n already the minimum degree for an n‐vertex graph G alone suffices to ensure the existence of a kth power of a Hamiltonian cycle. Here we show that under essentially the same degree assumption the addition of just O(n) random edges ensures the presence of the (k + 1)st power of a Hamiltonian cycle with probability close to one.     

Random partitions and edge-disjoint Hamiltonian cycles

Nash-Williams [1] proved that every graph with n   vertices and minimum degree n/2$n/2$ has at least ⌊5n/224⌋$\lfloor 5n/224\rfloor$ edge-disjoint Hamiltonian cycles. In [2], he raised the question of determining the maximum number of edge-disjoint Hamiltonian cycles, showing an upper bound of ⌊(n+4)/8⌋$\lfloor (n+4)/8\rfloor$.     

Powers of Hamiltonian paths in interval graphs

We give a simple proof that the obvious necessary conditions for a graph to contain the k^th power of a Hamiltonian path are sufficient for the class of interval graphs. The proof is based on showing that a greedy algorithm tests for the existence of Hamiltonian path powers in interval graphs. We will also discuss covers by powers of paths and analogues of the Hamiltonian completion number. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 31–38, 1998     

Hamiltonian cycles in k-partite graphs

Chen et al determined the minimum degree threshold for which a balanced $k$-partite graph has a Hamiltonian cycle. We give an asymptotically tight minimum degree condition for Hamiltonian cycles in arbitrary $k$-partite graphs in that all parts have at most $n/2$ vertices (a necessary condition). To do this, we first prove a general result that both simplifies the process of checking whether a graph $G$ is a robust expander and gives useful structural information in the case when $G$ is not a robust expander. Then we use this result to prove that any $k$-partite graph satisfying the minimum degree condition is either a robust expander or else contains a Hamiltonian cycle directly.     

The cycle structure of regular multipartite tournaments

A multipartite tournament is an orientation of a complete multipartite graph. A tournament is a multipartite tournament, each partite set of which contains exactly one vertex. Alspach (Canad. Math. Bull. 10 (1967) 283) proved that every regular tournament is arc-pancyclic. Although all partite sets of a regular multipartite tournament have the same cardinality, Alspach's theorem is not valid for regular multipartite tournaments. In this paper, we prove that if the cardinality common to all partite sets of a regular n-partite (n3) tournament T is odd, then every arc of T is in a cycle that contains vertices from exactly m partite sets for all m{3,4,…,n}. This result extends Alspach's theorem for regular tournaments to regular multipartite tournaments. We also examine the structure of cycles through arcs in regular multipartite tournaments.     

Edge‐disjoint Hamiltonian cycles in hypertournaments

We introduce a method for reducing k‐tournament problems, for k ≥ 3, to ordinary tournaments, that is, 2‐tournaments. It is applied to show that a k‐tournament on n ≥ k + 1 + 24d vertices (when k ≥ 4) or on n ≥ 30d + 2 vertices (when k = 3) has d edge‐disjoint Hamiltonian cycles if and only if it is d‐edge‐connected. Ironically, this is proved by ordinary tournament arguments although it only holds for k ≥ 3. We also characterizatize the pancyclic k‐tournaments, a problem posed by Gutin and Yeo.(Our characterization is slightly incomplete in that we prove it only for n large compared to k.). © 2005 Wiley Periodicals, Inc. J Graph Theory     

Complementary cycles in regular multipartite tournaments, where one cycle has length five

The vertex set of a digraph D is denoted by V(D). A c-partite tournament is an orientation of a complete c-partite graph.In 1999, Yeo conjectured that each regular c-partite tournament D with c≥4 and |V(D)|≥10 contains a pair of vertex disjoint directed cycles of lengths 5 and |V(D)|−5. In this paper we shall confirm this conjecture using a computer program for some cases.     

On certain Hamiltonian cycles in planar graphs

The problem is considered under which conditions a 4-connected planar or projective planar graph has a Hamiltonian cycle containing certain prescribed edges and missing certain forbidden edges. The results are applied to obtain novel lower bounds on the number of distinct Hamiltonian cycles that must be present in a 5-connected graph that is embedded into the plane or into the projective plane with face-width at least five. Especially, we show that every 5-connected plane or projective plane triangulation on n vertices with no non-contractible cyles of length less than five contains at least distinct Hamiltonian cycles. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 81–96, 1999     

Multicolored parallelisms of Hamiltonian cycles

A subgraph in an edge-colored graph is multicolored if all its edges receive distinct colors. In this paper, we prove that a complete graph on 2m+1 vertices K_2m+1 can be properly edge-colored with 2m+1 colors in such a way that the edges of K_2m+1 can be partitioned into m multicolored Hamiltonian cycles.     

Generating all cycles, chordless cycles, and Hamiltonian cycles with the principle of exclusion

An efficient method to generate all edge sets XE of a graph G=(V,E), which are vertex-disjoint unions of cycles, is presented. It can be tweaked to generate (i) all cycles, (ii) all cycles of cardinality 5, (iii) all chordless cycles, (iv) all Hamiltonian cycles.     

Three supplements to Reid’s theorem in multipartite tournaments

An n-partite tournament is an orientation of a complete n-partite graph. In this paper, we give three supplements to Reid’s theorem [K.B. Reid, Two complementary circuits in two-connected tournaments, Ann. Discrete Math. 27 (1985) 321-334] in multipartite tournaments. The first one is concerned with the lengths of cycles and states as follows: let D be an (α(D)+1)-strong n-partite tournament with n≥6, where α(D) is the independence number of D, then D contains two disjoint cycles of lengths 3 and n−3, respectively, unless D is isomorphic to the 7-tournament containing no transitive 4-subtournament (denoted by ). The second one is obtained by considering the number of partite sets that cycles pass through: every (α(D)+1)-strong n-partite tournament D with n≥6 contains two disjoint cycles which contain vertices from exactly 3 and n−3 partite sets, respectively, unless it is isomorphic to . The last one is about two disjoint cycles passing through all partite sets.     

Hamiltonian cycles in n-factor-critical graphs

A graph G is said to be n-factor-critical if G−S has a 1-factor for any SV(G) with |S|=n. In this paper, we prove that if G is a 2-connected n-factor-critical graph of order p with , then G is hamiltonian with some exceptions. To extend this theorem, we define a (k,n)-factor-critical graph to be a graph G such that G−S has a k-factor for any SV(G) with |S|=n. We conjecture that if G is a 2-connected (k,n)-factor-critical graph of order p with , then G is hamiltonian with some exceptions. In this paper, we characterize all such graphs that satisfy the assumption, but are not 1-tough. Using this, we verify the conjecture for k2.     

Hamiltonian paths in Cayley graphs

The classical question raised by Lovász asks whether every Cayley graph is Hamiltonian. We present a short survey of various results in that direction and make some additional observations. In particular, we prove that every finite group G has a generating set of size at most log₂|G|, such that the corresponding Cayley graph contains a Hamiltonian cycle. We also present an explicit construction of 3-regular Hamiltonian expanders.     

Finding large cycles in Hamiltonian graphs

We show how to find in Hamiltonian graphs a cycle of length n^{Ω(1/loglogn)}=exp(Ω(logn/loglogn)). This is a consequence of a more general result in which we show that if G has a maximum degree d and has a cycle with k vertices (or a 3-cyclable minor H with k vertices), then we can find in O(n³) time a cycle in G of length k^Ω(1/logd). From this we infer that if G has a cycle of length k, then one can find in O(n³) time a cycle of length k^{Ω(1/(log(n/k)+loglogn))}, which implies the result for Hamiltonian graphs. Our results improve, for some values of k and d, a recent result of Gabow (2004) [11] showing that if G has a cycle of length k, then one can find in polynomial time a cycle in G of length . We finally show that if G has fixed Euler genus g and has a cycle with k vertices (or a 3-cyclable minor H with k vertices), then we can find in polynomial time a cycle in G of length f(g)k^Ω(1), running in time O(n²) for planar graphs.     

On the girth of extremal graphs without shortest cycles

Let EX(ν;{C₃,…,C_n}) denote the set of graphs G of order ν that contain no cycles of length less than or equal to n which have maximum number of edges. In this paper we consider a problem posed by several authors: does G contain an n+1 cycle? We prove that the diameter of G is at most n−1, and present several results concerning the above question: the girth of G is g=n+1 if (i) ν≥n+5, diameter equal to n−1 and minimum degree at least 3; (ii) ν≥12, ν∉{15,80,170} and n=6. Moreover, if ν=15 we find an extremal graph of girth 8 obtained from a 3-regular complete bipartite graph subdividing its edges. (iii) We prove that if ν≥2n−3 and n≥7 the girth is at most 2n−5. We also show that the answer to the question is negative for ν≤n+1+⌊(n−2)/2⌋.     

Hamiltonian cycles and 2-dominating induced cycles in claw-free graphs

Let G = (V, E) be a connected graph. For a vertex subset , G[S] is the subgraph of G induced by S. A cycle C (a path, respectively) is said to be an induced cycle (path, respectively) if G[V(C)] = C (G[V(P)] = P, respectively). The distance between a vertex x and a subgraph H of G is denoted by , where d(x, y) is the distance between x and y. A subgraph H of G is called 2-dominating if d(x, H) ≤ 2 for all . An induced path P of G is said to be maximal if there is no induced path P′ satisfying and . In this paper, we assume that G is a connected claw-free graph satisfying the following condition: for every maximal induced path P of length p ≥ 2 with end vertices u, v it holds:

Packing complete multipartite graphs with 4‐cycles

In this paper we completely solve the problem of finding a maximum packing of any complete multipartite graph with edge‐disjoint 4‐cycles, and the minimum leaves are explicitly given. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 107–127, 2001     

How to avoid using the Regularity Lemma: Pósa’s conjecture revisited

In this paper we investigate how the use of the Regularity Lemma and the Blow-up Lemma can be avoided in certain extremal problems of dense graphs. We present the ideas for the following well-known Pósa conjecture on the square of a Hamiltonian cycle. In 1962 Pósa conjectured that any graph G of order n and minimum degree at least contains the square of a Hamiltonian cycle. In an earlier paper we proved this conjecture with the use of the Regularity Lemma-Blow-up Lemma method for n≥n₀ where n₀ is very large. Here we present another proof (and a general method) that avoids the use of the Regularity Lemma and thus the resulting n₀ is much smaller.