Long cycles in 4-connected planar graphs

Let G be a 4-connected planar graph on n vertices. Malkevitch conjectured that if G contains a cycle of length 4, then G contains a cycle of length k for every k∈{n,n−1,…,3}. This conjecture is true for every k∈{n,n−1,…,n−6} with k≥3. In this paper, we prove that G also has a cycle of length n−7 provided n≥10.     

哈密尔顿平面图最小平衡二部划分的上界

设$G（V,E）$是一个图,$V_{1},V_{2}$是$V$的一个二部划分,用$e（V_{1},V_{2}）$表示一条边的两个端点在不同划分里边的总数目,当$||V_{1}|-|V_{2}||leq 1$时,称$V_{1},V_{2}$是$V$的一个平衡二部划分。最小平衡二部划分是指寻找$G（V,E）$的一个平衡二部划分使得$e（V_{1},V_{2}）$最小。对于哈密尔顿平面图$G（V,E）$,研究了当Perfect-内部三角形最大边函数值与最小边函数值之差为$d$时,$e（V_{1},V_{2}）$最小值的上界与$d$之间的关系。     

Simultaneous diagonal flips in plane triangulations

Simultaneous diagonal flips in plane triangulations are investigated. It is proved that every triangulation with n ≥ 6 vertices has a simultaneous flip into a 4‐connected triangulation, and that the set of edges to be flipped can be computed in (n) time. It follows that every triangulation has a simultaneous flip into a Hamiltonian triangulation. This result is used to prove that for any two n‐vertex triangulations, there exists a sequence of (logn) simultaneous flips to transform one into the other. Moreover, Ω(log n) simultaneous flips are needed for some pairs of triangulations. The total number of edges flipped in this sequence is (n). The maximum size of a simultaneous flip is then studied. It is proved that every triangulation has a simultaneous flip of at least edges. On the other hand, every simultaneous flip has at most n ? 2 edges, and there exist triangulations with a maximum simultaneous flip of edges. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 307–330, 2007     

Generating even triangulations of the projective plane

We shall determine the 20 families of irreducible even triangulations of the projective plane. Every even triangulation of the projective plane can be obtained from one of them by a sequence of even‐splittings and attaching octahedra, both of which were first given by Batagelj 2 . © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 333–349, 2007     

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.     

Loose Hamilton cycles in hypergraphs

We prove that any k-uniform hypergraph on n vertices with minimum degree at least contains a loose Hamilton cycle. The proof strategy is similar to that used by Kühn and Osthus for the 3-uniform case. Though some additional difficulties arise in the k-uniform case, our argument here is considerably simplified by applying the recent hypergraph blow-up lemma of Keevash.     

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 cycles in line graphs of 3-hypergraphs

We prove that every 52-connected line graph of a rank 3 hypergraph is Hamiltonian. This is the first result of this type for hypergraphs of bounded rank other than ordinary 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     

On the number of hamiltonian cycles in triangulations with few separating triangles

In this article, we investigate the number of hamiltonian cycles in triangulations. We improve a lower bound of for the number of hamiltonian cycles in triangulations without separating triangles (4‐connected triangulations) by Hakimi, Schmeichel, and Thomassen to a linear lower bound and show that a linear lower bound even holds in the case of triangulations with one separating triangle. We confirm their conjecture about the number of hamiltonian cycles in triangulations without separating triangles for up to 25 vertices and give computational results and constructions for triangulations with a small number of hamiltonian cycles and 1–5 separating triangles.     

A note on the 2-power of Hamilton cycles

We determine the maximum number of edges of a graph without containing the 2-power of a Hamilton cycle. This extends a well-known theorem of Ore in 1961 concerning the maximum number of edges of a graph without containing a Hamilton cycle.     

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 digraphs of unitary matrices

A set S⊆V is called a q⁺-set (q^--set, respectively) if S has at least two vertices and, for every u∈S, there exists v∈S,v≠u such that N⁺(u)∩N⁺(v)≠∅ (N^-(u)∩N^-(v)≠∅, respectively). A digraph D is called s-quadrangular if, for every q⁺-set S, we have |∪{N⁺(u)∩N⁺(v):u≠v,u,v∈S}|?|S| and, for every q^--set S, we have |∪{N^-(u)∩N^-(v):u,v∈S)}?|S|. We conjecture that every strong s-quadrangular digraph has a Hamilton cycle and provide some support for this conjecture.     

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.     

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).     

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.     

Hamilton cycles,avoiding prescribed arcs,in close-to-regular tournaments

The local irregularity of a digraph D is defined as i_l(D) = max {|d⁺ (x) − d⁻ (x)| : x ϵ V(D)}. Let T be a tournament, let Γ = {V₁, V₂, …, V_c} be a partition of V(T) such that |V₁| ≥ |V₂| ≥ … ≥ |V_c|, and let D be the multipartite tournament obtained by deleting all the arcs with both end points in the same set in Γ. We prove that, if |V(T)| ≥ max{2i_l(T) + 2|V₁| + 2|V₂| − 2, i_l(T) + 3|V₁| − 1}, then D is Hamiltonian. Furthermore, if T is regular (i.e., i_l(T) = 0), then we state slightly better lower bounds for |V(T)| such that we still can guarantee that D is Hamiltonian. Finally, we show that our results are best possible. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 123–136, 1999