Compatible Hamilton cycles in random graphs

A graph is Hamiltonian if it contains a cycle passing through every vertex. One of the cornerstone results in the theory of random graphs asserts that for edge probability , the random graph G(n, p) is asymptotically almost surely Hamiltonian. We obtain the following strengthening of this result. Given a graph , an incompatibility system over G is a family where for every , the set F_v is a set of unordered pairs . An incompatibility system is Δ‐bounded if for every vertex v and an edge e incident to v, there are at most Δ pairs in F_v containing e. We say that a cycle C in G is compatible with if every pair of incident edges of C satisfies . This notion is partly motivated by a concept of transition systems defined by Kotzig in 1968, and can be used as a quantitative measure of robustness of graph properties. We prove that there is a constant such that the random graph with is asymptotically almost surely such that for any μnp‐bounded incompatibility system over G, there is a Hamilton cycle in G compatible with . We also prove that for larger edge probabilities , the parameter μ can be taken to be any constant smaller than . These results imply in particular that typically in G(n, p) for , for any edge‐coloring in which each color appears at most μnp times at each vertex, there exists a properly colored Hamilton cycle. Furthermore, our proof can be easily modified to show that for any edge‐coloring of such a random graph in which each color appears on at most μnp edges, there exists a Hamilton cycle in which all edges have distinct colors (i.e., a rainbow Hamilton cycle). © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 533–557, 2016     

Hamilton cycles in random graphs and directed graphs

We prove that almost every digraph D_{2–in, 2–out} is Hamiltonian. As a corollary we obtain also that almost every graph G_4–out is Hamiltonian. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16: 369–401, 2000     

Powers of Hamilton cycles in random graphs and tight Hamilton cycles in random hypergraphs

We show that for every there exists C > 0 such that if then asymptotically almost surely the random graph contains the k^th power of a Hamilton cycle. This determines the threshold for appearance of the square of a Hamilton cycle up to the logarithmic factor, improving a result of Kühn and Osthus. Moreover, our proof provides a randomized quasi‐polynomial algorithm for finding such powers of cycles. Using similar ideas, we also give a randomized quasi‐polynomial algorithm for finding a tight Hamilton cycle in the random k‐uniform hypergraph for . The proofs are based on the absorbing method and follow the strategy of Kühn and Osthus, and Allen et al. The new ingredient is a general Connecting Lemma which allows us to connect tuples of vertices using arbitrary structures at a nearly optimal value of p. Both the Connecting Lemma and its proof, which is based on Janson's inequality and a greedy embedding strategy, might be of independent interest.     

Hamilton cycles in random lifts of graphs

An n-lift of a graph K is a graph with vertex set V(K)×[n], and for each edge (i,j)E(K) there is a perfect matching between {i}×[n] and {j}×[n]. If these matchings are chosen independently and uniformly at random then we say that we have a random n-lift. We show that there are constants h₁,h₂ such that if h≥h₁ then a random n-lift of the complete graph K_h is hamiltonian and if h≥h₂ then a random n-lift of the complete bipartite graph K_h,h is hamiltonian .     

Rainbow matchings and Hamilton cycles in random graphs

Let be drawn uniformly from all m‐edge, k‐uniform, k‐partite hypergraphs where each part of the partition is a disjoint copy of . We let be an edge colored version, where we color each edge randomly from one of colors. We show that if and where K is sufficiently large then w.h.p. there is a rainbow colored perfect matching. I.e. a perfect matching in which every edge has a different color. We also show that if n is even and where K is sufficiently large then w.h.p. there is a rainbow colored Hamilton cycle in . Here denotes a random edge coloring of with n colors. When n is odd, our proof requires for there to be a rainbow Hamilton cycle. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 503–523, 2016     

Edge‐disjoint Hamilton cycles in random graphs

We show that provided we can with high probability find a collection of edge‐disjoint Hamilton cycles in , plus an additional edge‐disjoint matching of size if is odd. This is clearly optimal and confirms, for the above range of p, a conjecture of Frieze and Krivelevich. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 397–445, 2015     

Hamilton cycles containing randomly selected edges in random regular graphs

In previous papers the authors showed that almost all d‐regular graphs for d≤3 are hamiltonian. In the present paper this result is generalized so that a set of j oriented root edges have been randomly specified for the cycle to contain. The Hamilton cycle must be orientable to agree with all of the orientations on the j root edges. It is shown that the requisite Hamilton cycle almost surely exists if and the limiting probability distribution at the threshold is determined when d=3. It is a corollary (in view of results elsewhere) that almost all claw‐free cubic graphs are hamiltonian. There is a variation in which an additional cyclic ordering on the root edges is imposed which must also agree with their ordering on the Hamilton cycle. In this case, the required Hamilton cycle almost surely exists if j=o(n^2/5). The method of analysis is small subgraph conditioning. This gives results on contiguity and the distribution of the number of Hamilton cycles which imply the facts above. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 128–147, 2001     

Packing,counting and covering Hamilton cycles in random directed graphs

In this paper we study the chaotic behavior of the heat semigroup generated by the Dunkl-Laplacian on weighted L ^p spaces. In the case of the heat semigroup associated to the standard Laplacian we obtain a complete picture on the spaces L ^p (R ⁿ , (φ _iρ (x))² dx) where φ _iρ is the Euclidean spherical function. The behavior is very similar to the case of the Laplace–Beltrami operator on non-compact Riemannian symmetric spaces studied by Pramanik and Sarkar.     

Hamilton cycles in claw-heavy graphs

A graph G on n≥3 vertices is called claw-heavy if every induced claw (K_1,3) of G has a pair of nonadjacent vertices such that their degree sum is at least n. In this paper we show that a claw-heavy graph G has a Hamilton cycle if we impose certain additional conditions on G involving numbers of common neighbors of some specific pair of nonadjacent vertices, or forbidden induced subgraphs. Our results extend two previous theorems of Broersma, Ryjá?ek and Schiermeyer [H.J. Broersma, Z. Ryjá?ek, I. Schiermeyer, Dirac’s minimum degree condition restricted to claws, Discrete Math. 167-168 (1997) 155-166], on the existence of Hamilton cycles in 2-heavy graphs.     

Hamilton cycles in claw-free graphs

Bondy conjectured that if G is a k-connected graph of order n such that for any (k + 1)-independent set / of G, then the subgraph outside any longest cycle contains no path of length k ? 1. In this paper, we are going to prove that, if G is a k-connected claw-free (K_1,3-free) graph of order n such that for any (k + 1)-independent set /, then G contains a Hamilton cycle. The theorem in this paper implies Bondy's conjecture in the case of claw-free graphs.     

Hamilton cycles in restricted block-intersection graphs

As part of our main result we prove that the blocks of any sufficiently large BIBD(v, 4, λ) can be circularly ordered so that consecutive blocks intersect in exactly one point, i.e., that the 1-block-intersection graphs of such designs are Hamiltonian. In fact, we prove that such graphs are Hamilton-connected. We also consider {1, 2}-block-intersection graphs, in which adjacent vertices have either one or two points in common between their corresponding blocks. These graphs are Hamilton-connected for all sufficiently large BIBD(v, k, λ) with \({k \in \{4,5,6\}}\).     

Edge disjoint Hamilton cycles in graphs

Let G be a graph of order n and k ≥ 0 an integer. It is conjectured in [8] that if for any two vertices u and v of a 2(k + 1)‐connected graph G,d _G (u,v) = 2 implies that max{d(u;G), d(v;G)} ≥ (n/2) + 2k, then G has k + 1 edge disjoint Hamilton cycles. This conjecture is true for k = 0, 1 (see cf. [3] and [8]). It will be proved in this paper that the conjecture is true for every integer k ≥ 0. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 8–20, 2000     

Tight Hamilton cycles in random hypergraphs

We give an algorithmic proof for the existence of tight Hamilton cycles in a random r‐uniform hypergraph with edge probability for every . This partly answers a question of Dudek and Frieze (Random Struct Algor 42 (2013), 374–385), who used a second moment method to show that tight Hamilton cycles exist even for where arbitrary slowly, and for . The method we develop for proving our result applies to related problems as well. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 446–465, 2015     

On Hamilton cycles in certain planar graphs

Let G be a 2-connected plane graph with outer cycle X_G such that for every minimal vertex cut S of G with |S| ≤ 3, every component of G\S contains a vertex of X_G. A sufficient condition for G to be Hamiltonian is presented. This theorem generalizes both Tutte's theorem that every 4-connected planar graph is Hamiltonian, as well as a recent theorem of Dillencourt about NST-triangulations. A linear algorithm to find a Hamilton cycle can be extracted from the proof. One corollary is that a 4-connected planar graph with the vertices of a triangle deleted is Hamiltonian. © 1996 John Wiley & Sons, Inc.     

Hamilton cycles in regular 3-connected graphs

We show in this paper that for k63, every 3-connected, k-regular simple graph on at most vertices is hamiltonian.     

Hamilton cycles in strong products of graphs

We prove that the strong product of any n connected graphs of maximum degree at most n contains a Hamilton cycle. In particular, G^Δ(G) is hamiltonian for each connected graph G, which answers in affirmative a conjecture of Bermond, Germa, and Heydemann. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 299–321, 2005