Symmetric Hamilton cycle decompositions of the complete graph

We construct a new symmetric Hamilton cycle decomposition of the complete graph K_n for odd n > 7. © 2003 Wiley Periodicals, Inc.     

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     

Each maximal planar graph with exactly two separating triangles is Hamiltonian

A classical result of Whitney states that each maximal planar graph without separating triangles is Hamiltonian, where a separating triangle is a triangle whose removal separates the graph. Chen [Any maximal planar graph with only one separating triangle is Hamiltonian J. Combin. Optim. 7 (2003) 79-86] proved that any maximal planar graph with only one separating triangle is still Hamiltonian. In this paper, it is shown that the conclusion of Whitney's Theorem still holds if there are exactly two separating triangles.     

邻接树图是哈密尔顿图猜想的一个等价命题

本文给出了简单图的邻接树图是哈密尔顿图”猜想的等价命题,阐明只需证明该猜想对2－连通图成立即可,另外,我们给出了该猜想一种特殊情形的构造性证明。     

Hamiltonian threshold for strong products of graphs

We prove that the strong product of any at least non‐trivial connected graphs of maximum degree at most Δ is pancyclic. The obtained result is asymptotically best possible since the strong product of ?(ln 2)D? stars K_1,D is not even hamiltonian. © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 314–328, 2008     

The hamiltonian index of a 2-connected graph

Let G be a graph. Then the hamiltonian index h(G) of G is the smallest number of iterations of line graph operator that yield a hamiltonian graph. In this paper we show that for every 2-connected simple graph G that is not isomorphic to the graph obtained from a dipole with three parallel edges by replacing every edge by a path of length l≥3. We also show that for any two 2-connected nonhamiltonian graphs G and with at least 74 vertices. The upper bounds are all sharp.     

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.     

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.     

On factors of 4‐connected claw‐free graphs*

We consider the existence of several different kinds of factors in 4‐connected claw‐free graphs. This is motivated by the following two conjectures which are in fact equivalent by a recent result of the third author. Conjecture 1 (Thomassen): Every 4‐connected line graph is hamiltonian, i.e., has a connected 2‐factor. Conjecture 2 (Matthews and Sumner): Every 4‐connected claw‐free graph is hamiltonian. We first show that Conjecture 2 is true within the class of hourglass‐free graphs, i.e., graphs that do not contain an induced subgraph isomorphic to two triangles meeting in exactly one vertex. Next we show that a weaker form of Conjecture 2 is true, in which the conclusion is replaced by the conclusion that there exists a connected spanning subgraph in which each vertex has degree two or four. Finally we show that Conjectures 1 and 2 are equivalent to seemingly weaker conjectures in which the conclusion is replaced by the conclusion that there exists a spanning subgraph consisting of a bounded number of paths © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 125–136, 2001     

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     

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.     

Cyclic even cycle systems of the complete graph

In this article, it is proved that for each even integer m?4 and each admissible value n with n>2m, there exists a cyclic m‐cycle system of K_n, which almost resolves the existence problem for cyclic m‐cycle systems of K_n with m even. © 2011 Wiley Periodicals, Inc. J Combin Designs 20:23–39, 2012     

Cyclic cycle systems of the complete multipartite graph

In this paper, we study the existence problem for cyclic $?$‐cycle decompositions of the graph $K_m\left[n\right]$, the complete multipartite graph with $m$ parts of size $n$, and give necessary and sufficient conditions for their existence in the case that $2?|\left(m?1\right)n$.     

K-Factors and Hamilton Cycles in Graphs

We discuss k-factors and Hamiltonian Graphs in graph theory. We prove a general version of the conjecture by R. Haggkvist; as a result, we prove two extended versions of two well-known theorems due to O. Ore and B. Jachson, respectively.     

PANCYCLICITY IN LINE GRAPHS

1IntroductionWeuseBondyandMurtyl3]forterminologyand..ta'ti..notdefinedhereandconsidersimpleconnectedgraphsonly.AcircuitCofagraphGisanontrivialconnectedeuleriansubgraphofG.Aspanningcircuit,orbrieflyS-circuit,ofagraphGisacircuitthatcontainsallvenicesofG.AdominatingcircuitorD-circuitofGisacircuitsuchthateveryedgeofGisincidentwithatleastonevertexofthecircuit.AgraphofordernispancyclicifitcontainsallcyclesoflengthIfor3515n.IfCisacircuitofG,thenP(C)denotesthenumberOfedgesofGincidentwithatleas…     

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.     

The Ihara zeta function of the complement of a semiregular bipartite graph

We study the Ihara zeta function of the complement of a semiregular bipartite graph. A factorization formula for the Ihara zeta function is derived via which the number of spanning trees is computed. For a class of complements of semiregular bipartite graphs, it is shown that they have the same Ihara zeta function if and only if they are cospectral.     

Hamilton cycle decomposition of 6‐regular circulants of odd order

The circulant G = C(n,S), where , is the graph with vertex set Z_n and edge set . It is shown that for n odd, every 6‐regular connected circulant C(n, S) is decomposable into Hamilton cycles. © 2006 Wiley Periodicals, Inc. J Combin Designs