On the Pósa-Seymour conjecture

Paul Seymour conjectured that any graph G of order n and minimum degree at least contains the k^th power of a Hamilton cycle. We prove the following approximate version. For any ϵ ≥ 0 and positive integer k, there is an n₀ such that, if G has order n ≥ n₀ and minimum degree at least $(\frac{k}{k+1} + \epsilon )n$, then G contains the k^th power of a Hamilton cycle. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 167–176, 1998     

The dichromatic number of a digraph

In this paper the concept of dichromatic number of a digraph which is a generalization of the chromatic number of a graph is introduced. The dichromatic number of a digraph D is defined as the minimum number of colours required to colour the vertices of D in such a way that the chromatic classes induce acyclic subdigraphs in D. Some results relating the dichromatic number of D with the existence of cycles of special lengths in D are presented. Contributions to chromatic theory are also obtained. In particular, we generalize the theorem due to P. Erdös and A. Hajnal (Acta Math. Acad. Sci. Hungar.17 (1966), 61–99) which states the existence of odd cycles of length ≥_χ(G) ? 1 in any graph G.     

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.     

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     

Sparse hamiltonian 2-decompositions together with exact count of numerous Hamilton cycles

We construct multigraphs of any large order with as few as only four 2-decompositions into Hamilton cycles or only two 2-decompositions into Hamilton paths. Nevertheless, some of those multigraphs are proved to have exponentially many Hamilton cycles (Hamilton paths). Two families of large simple graphs are constructed. Members in one class have exactly 16 hamiltonian pairs and in another class exactly four traceable pairs. These graphs also have exponentially many Hamilton cycles and Hamilton paths, respectively. The exact numbers of (Hamilton) cycles and paths are expressed in terms of Lucas- or Fibonacci-like numbers which count 2-independent vertex (or edge) subsets on the n-path or n-cycle. A closed formula which counts Hamilton cycles in the square of the n-cycle is found for n≥5. The presented results complement, improve on, or extend the corresponding well-known Thomason’s results.     

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.     

Symmetric Hamilton cycle decompositions of complete graphs minus a 1‐factor

Let n≥2 be an integer. The complete graph K_n with a 1‐factor F removed has a decomposition into Hamilton cycles if and only if n is even. We show that K_n−F has a decomposition into Hamilton cycles which are symmetric with respect to the 1‐factor F if and only if n≡2, 4 mod 8. We also show that the complete bipartite graph K_{n, n} has a symmetric Hamilton cycle decomposition if and only if n is even, and that if F is a 1‐factor of K_{n, n}, then K_{n, n}−F has a symmetric Hamilton cycle decomposition if and only if n is odd. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:1‐15, 2010     

Half-integral packing of odd cycles through prescribed vertices

The well-known theorem of Erd?s-Pósa says that a graph G has either k disjoint cycles or a vertex set X of order at most f(k) for some function f such that G\X is a forest. Starting with this result, there are many results concerning packing and covering cycles in graph theory and combinatorial optimization. In this paper, we discuss packing disjoint S-cycles, i.e., cycles that are required to go through a set S of vertices. For this problem, Kakimura-Kawarabayashi-Marx (2011) and Pontecorvi-Wollan (2010) recently showed the Erd?s-Pósa-type result holds. We further try to generalize this result to packing S-cycles of odd length. In contrast to packing S-cycles, the Erd?s-Pósa-type result does not hold for packing odd S-cycles. We then relax packing odd S-cycles to half-integral packing, and show the Erd?s-Pósa-type result for the half-integral packing of odd S-cycles, which is a generalization of Reed (1999) when S=V. That is, we show that given an integer k and a vertex set S, a graph G has either 2k odd S-cycles so that each vertex is in at most two of these cycles, or a vertex set X of order at most f(k) (for some function f) such that G\X has no odd S-cycle.     

Congruences for rational points on varieties over finite fields

We prove the existence of rational points on singular varieties over finite fields arising as degenerations of smooth proper varieties with trivial Chow group of 0-cycles. We also obtain congruences for the number of rational points of singular varieties appearing as fibres of a proper family with smooth total and base space and such that the Chow group of 0-cycles of the generic fibre is trivial. In particular this leads to a vast generalization of the classical Chevalley-Warning theorem. The above results are obtained as special cases of our main theorem which can be viewed as a relative version of a theorem of H. Esnault on the number of rational points of smooth proper varieties over finite fields with trivial Chow group of 0-cycles.     

Random directed graphs are robustly Hamiltonian

A classical theorem of Ghouila‐Houri from 1960 asserts that every directed graph on n vertices with minimum out‐degree and in‐degree at least contains a directed Hamilton cycle. In this paper we extend this theorem to a random directed graph , that is, a directed graph in which every ordered pair (u, v) becomes an arc with probability p independently of all other pairs. Motivated by the study of resilience of properties of random graphs, we prove that if , then a.a.s. every subdigraph of with minimum out‐degree and in‐degree at least contains a directed Hamilton cycle. The constant 1/2 is asymptotically best possible. Our result also strengthens classical results about the existence of directed Hamilton cycles in random directed graphs. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 345–362, 2016     

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.     

On short cycles in triangle-free oriented graphs

An orientation of a simple graph is referred to as an oriented graph. Caccetta and Häggkvist conjectured that any digraph on n vertices with minimum outdegree d contains a directed cycle of length at most ?n/d?. In this paper, we consider short cycles in oriented graphs without directed triangles. Suppose that α0 is the smallest real such that every n-vertex digraph with minimum outdegree at least α₀n contains a directed triangle. Let ε < (3 ? 2α₀)/(4 ? 2α₀) be a positive real. We show that if D is an oriented graph without directed triangles and has minimum outdegree and minimum indegree at least (1/(4 ? 2α₀)+ε)|D|, then each vertex of D is contained in a directed cycle of length l for each 4 ≤ l < (4 ? 2α₀)ε|D|/(3 ? 2α₀) + 2.     

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.     

Edge disjoint cycles through specified vertices

We give a sufficient condition for a simple graph G to have k pairwise edge‐disjoint cycles, each of which contains a prescribed set W of vertices. The condition is that the induced subgraph G[W] be 2k‐connected, and that for any two vertices at distance two in G[W], at least one of the two has degree at least |V(G)|/2 + 2(k ? 1) in G. This is a common generalization of special cases previously obtained by Bollobás/Brightwell (where k = 1) and Li (where W = V(G)). A key lemma is of independent interest. Let G be the complement of a bipartite graph with partite sets X, Y. If G is 2k connected, then G contains k Hamilton cycles that are pairwise edge‐disjoint except for edges in G[Y]. © 2005 Wiley Periodicals, Inc. J Graph Theory     

On cycles in regular 3-partite tournaments

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 1991, Jian-zhong Wang conjectured that every arc of a regular 3-partite tournament D is contained in directed cycles of all lengths 3,6,9,…,|V(D)|. This conjecture is not valid, because for each integer t with 3?t?|V(D)|, there exists an infinite family of regular 3-partite tournaments D such that at least one arc of D is not contained in a directed cycle of length t.In this paper, we prove that every arc of a regular 3-partite tournament with at least nine vertices is contained in a directed cycle of length m, m+1, or m+2 for 3?m?5, and we conjecture that every arc of a regular 3-partite tournament is contained in a directed cycle of length m, (m+1), or (m+2) for each m∈{3,4,…,|V(D)|-2}.It is known that every regular 3-partite tournament D with at least six vertices contains directed cycles of lengths 3, |V(D)|-3, and |V(D)|. We show that every regular 3-partite tournament D with at least six vertices also has a directed cycle of length 6, and we conjecture that each such 3-partite tournament contains cycles of all lengths 3,6,9,…,|V(D)|.     

Hamilton decompositions of graphs with primitive complements

A k-factor of a graph is a k-regular spanning subgraph. A Hamilton cycle is a connected 2-factor. A graph G is said to be primitive if it contains no k-factor with 1≤k<Δ(G). A Hamilton decomposition of a graph G is a partition of the edges of G into sets, each of which induces a Hamilton cycle. In this paper, by using the amalgamation technique, we find necessary and sufficient conditions for the existence of a 2x-regular graph G on n vertices which:

1.

has a Hamilton decomposition, and

2.

has a complement in K_n that is primitive.

This extends the conditions studied by Hoffman, Rodger, and Rosa [D.G. Hoffman, C.A. Rodger, A. Rosa, Maximal sets of 2-factors and Hamiltonian cycles, J. Combin. Theory Ser. B 57 (1) (1993) 69-76] who considered maximal sets of Hamilton cycles and 2-factors. It also sheds light on construction approaches to the Hamilton-Waterloo problem.     

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.     

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.     

Connected graphs as subgraphs of Cayley graphs: Conditions on Hamiltonicity

Let Γ be a connected simple graph, let V(Γ) and E(Γ) denote the vertex-set and the edge-set of Γ, respectively, and let n=|V(Γ)|. For 1≤i≤n, let e_i be the element of elementary abelian group which has 1 in the ith coordinate, and 0 in all other coordinates. Assume that V(Γ)={e_i∣1≤i≤n}. We define a set Ω by Ω={e_i+e_j∣{e_i,e_j}∈E(Γ)}, and let Cay_Γ denote the Cayley graph over with respect to Ω. It turns out that Cay_Γ contains Γ as an isometric subgraph. In this paper, the relations between the spectra of Γ and Cay_Γ are discussed. Some conditions on the existence of Hamilton paths and cycles in Γ are obtained.