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.     

Properties of Hamilton cycles of circuit graphs of matroids

Let G be a circuit graph of a connected matroid. P. Li and G. Liu [Comput. Math. Appl., 2008, 55: 654–659] proved that G has a Hamilton cycle including e and another Hamilton cycle excluding e for any edge e of G if G has at least four vertices. This paper proves that G has a Hamilton cycle including e and excluding e′ for any two edges e and e′ of G if G has at least five vertices. This result is best possible in some sense. An open problem is proposed in the end of this paper.     

Decompositions of complete graphs into triangles and Hamilton cycles

For all odd integers n ≥ 1, let G_n denote the complete graph of order n, and for all even integers n ≥ 2 let G_n denote the complete graph of order n with the edges of a 1‐factor removed. It is shown that for all non‐negative integers h and t and all positive integers n, G_n can be decomposed into h Hamilton cycles and t triangles if and only if nh + 3t is the number of edges in G_n. © 2004 Wiley Periodicals, Inc.     

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     

Hamilton paths and cycles in vertex-transitive graphs of order

It is shown that every connected vertex-transitive graph of order 6p, where p is a prime, contains a Hamilton path. Moreover, it is shown that, except for the truncation of the Petersen graph, every connected vertex-transitive graph of order 6p which is not genuinely imprimitive contains a Hamilton cycle.     

Hamilton connectivity of line graphs and claw‐free graphs

Let G be a graph and let V₀ = {ν∈ V(G): d_G(ν) = 6}. We show in this paper that: (i) if G is a 6‐connected line graph and if |V₀| ≤ 29 or G[V₀] contains at most 5 vertex disjoint K₄'s, then G is Hamilton‐connected; (ii) every 8‐connected claw‐free graph is Hamilton‐connected. Several related results known before are generalized. © 2005 Wiley Periodicals, Inc. J Graph Theory     

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     

Highly-connected planar cubic graphs with few or many Hamilton cycles

In this paper we consider the number of Hamilton cycles in planar cubic graphs of high cyclic edge-connectivity, answering two questions raised by Chia and Thomassen (2012) about extremal graphs in these families. In particular, we find families of cyclically 5-edge-connected planar cubic graphs with more Hamilton cycles than the generalized Petersen graphs $P(2n,2)$. The graphs themselves are fullerene graphs that correspond to certain carbon molecules known as nanotubes—more precisely, the family consists of the zigzag nanotubes of (fixed) width 5and increasing length. In order to count the Hamilton cycles in the nanotubes, we develop methods inspired by the transfer matrices of statistical physics. We outline how these methods can be adapted to count the Hamilton cycles in nanotubes of greater (but still fixed) width, with the caveat that the resulting expressions involve matrix powers. We also consider cyclically 4-edge-connected planar cubic graphs with few Hamilton cycles, and exhibit an infinite family of such graphs each with exactly 4 Hamilton cycles. Finally we consider the “other extreme” for these two classes of graphs, thus investigating cyclically 4-edge-connected planar cubic graphs with many Hamilton cycles and the cyclically 5-edge-connected planar cubic graphs with few Hamilton cycles. In each of these cases, we present partial results, examples and conjectures regarding the graphs with few or many Hamilton cycles.     

Hourglasses and Hamilton cycles in 4‐connected claw‐free graphs

We show that if G is a 4‐connected claw‐free graph in which every induced hourglass subgraph S contains two non‐adjacent vertices with a common neighbor outside S, then G is hamiltonian. This extends the fact that 4‐connected claw‐free, hourglass‐free graphs are hamiltonian, thus proving a broader special case of a conjecture by Matthews and Sumner. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 267–276, 2005     

Disjoint Hamilton cycles in the random geometric graph

We consider the standard random geometric graph process in which n vertices are placed at random on the unit square and edges are sequentially added in increasing order of edge‐length. For fixed k?1, weprove that the first edge in the process that creates a k‐connected graph coincides a.a.s. with the first edge that causes the graph to contain k/2 pairwise edge‐disjoint Hamilton cycles (for even k), or (k?1)/2 Hamilton cycles plus one perfect matching, all of them pairwise edge‐disjoint (for odd k). This proves and extends a conjecture of Krivelevich and M ler. In the special case when k = 2, our result says that the first edge that makes the random geometric graph Hamiltonian is a.a.s. exactly the same one that gives 2‐connectivity, which answers a question of Penrose. (This result appeared in three independent preprints, one of which was a precursor to this article.) We prove our results with lengths measured using the ?_p norm for any p>1, and we also extend our result to higher dimensions. © 2011 Wiley Periodicals, Inc. J Graph Theory 68:299‐322, 2011     

Maximal sets of Hamilton cycles in complete multipartite graphs IV

Finding the values of μ for which there exists a maximal set of μ edge-disjoint Hamilton cycles in the complete multipartite graph $K_n^p$ has been considered in papers for over 20 years. This paper finally settles the problem by finding such a set in the last remaining open case, namely where μ is as small as possible (so its existence was still in doubt) when $n=3$ and the number of parts, p, is 3 (mod 4).     

Hamilton cycles and paths in vertex-transitive graphs—Current directions

In this article current directions in solving Lovász’s problem about the existence of Hamilton cycles and paths in connected vertex-transitive graphs are given.     

Hamilton cycles in plane triangulations

We extend Whitney's Theorem that every plane triangulation without separating triangles is hamiltonian by allowing some separating triangles. More precisely, we define a decomposition of a plane triangulation G into 4‐connected ‘pieces,’ and show that if each piece shares a triangle with at most three other pieces then G is hamiltonian. We provide an example to show that our hypothesis that each piece shares a triangle with at most three other pieces' cannot be weakened to ‘four other pieces.’ As part of our proof, we also obtain new results on Tutte cycles through specified vertices in planar graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 138–150, 2002     

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.     

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 cycle rich two‐factorizations of complete graphs

For all integers n ≥ 5, it is shown that the graph obtained from the n‐cycle by joining vertices at distance 2 has a 2‐factorization is which one 2‐factor is a Hamilton cycle, and the other is isomorphic to any given 2‐regular graph of order n. This result is used to prove several results on 2‐factorizations of the complete graph K_n of order n. For example, it is shown that for all odd n ≥ 11, K_n has a 2‐factorization in which three of the 2‐factors are isomorphic to any three given 2‐regular graphs of order n, and the remaining 2‐factors are Hamilton cycles. For any two given 2‐regular graphs of even order n, the corresponding result is proved for the graph K_n ‐ I obtained from the complete graph by removing the edges of a 1‐factor. © 2004 Wiley Periodicals, Inc.     

Two Hamiltonian cycles

If the line graph of a graph G decomposes into Hamiltonian cycles, what is G? We answer this question for decomposition into two cycles.