Hamilton weights and Petersen minors*

A (1, 2)‐eulerian weight w of a cubic graph is called a Hamilton weight if every faithful circuit cover of the graph with respect to w is a set of two Hamilton circuits. Let G be a 3‐connected cubic graph containing no Petersen minor. It is proved in this paper that G admits a Hamilton weight if and only if G can be obtained from K₄ by a series of Δ?Y‐operations. As a byproduct of the proof of the main theorem, we also prove that if G is a permutation graph and w is a (1,2)‐eulerian weight of G such that (G, w) is a critical contra pair, then the Petersen minor appears “almost everywhere” in the graph G. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 197–219, 2001     

New Local Conditions for a Graph to be Hamiltonian

For a vertex w of a graph G the ball of radius 2 centered at w is the subgraph of G induced by the set M₂(w) of all vertices whose distance from w does not exceed 2. We prove the following theorem: Let G be a connected graph where every ball of radius 2 is 2-connected and d(u)+d(v)≥|M₂(w)|−1 for every induced path uwv. Then either G is hamiltonian or for some p≥2 where ∨ denotes join. As a corollary we obtain the following local analogue of a theorem of Nash-Williams: A connected r-regular graph G is hamiltonian if every ball of radius 2 is 2-connected and for each vertex w of G. Supported by the Swedish Research Council (VR)     

On stability of the hamiltonian index under contractions and closures

The hamiltonian index of a graph G is the smallest integer k such that the k‐th iterated line graph of G is hamiltonian. We first show that, with one exceptional case, adding an edge to a graph cannot increase its hamiltonian index. We use this result to prove that neither the contraction of an A_G(F)‐contractible subgraph F of a graph G nor the closure operation performed on G (if G is claw‐free) affects the value of the hamiltonian index of a graph G. AMS Subject Classification (2000): 05C45, 05C35. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Closure for the property of having a hamiltonian prism

We prove that a graph G of order n has a hamiltonian prism if and only if the graph Cl_4n/3–4/3(G) has a hamiltonian prism where Cl_4n/3–4/3(G) is the graph obtained from G by sequential adding edges between non‐adjacent vertices whose degree sum is at least 4n/3–4/3. We show that this cannot be improved to less than 4n/3–5. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 209–220, 2007     

On s‐Hamiltonian Line Graphs

For an integer s ≥ 0, a graph G is s‐hamiltonian if for any vertex subset with |S^′| ≤ s, G ‐ S^′ is hamiltonian. It is well known that if a graph G is s‐hamiltonian, then G must be (s+2)‐connected. The converse is not true, as there exist arbitrarily highly connected nonhamiltonian graphs. But for line graphs, we prove that when s ≥ 5, a line graph is s‐hamiltonian if and only if it is (s+2)‐connected.     

A Remark on Hamiltonian Cycles

Let G be an undirected and simple graph on n vertices. Let ω, α and χ denote the number of components, the independence number and the connectivity number of G. G is called a 1-tough graph if ω(G – S) ? |S| for any subset S of V(G) such that ω(G ? S) > 1. Let σ₂ = min {d(v) + d(w)|v and w are nonadjacent}. Note that the difference α - χ in 1-tough graph may be made arbitrary large. In this paper we prove that any 1-tough graph with σ₂ > n + χ - α is hamiltonian.     

Heavy cycles passing through some specified vertices in weighted graphs

A weighted graph is one in which every edge e is assigned a nonnegative number, called the weight of e. The sum of the weights of the edges incident with a vertex υ is called the weighted degree of υ. The weight of a cycle is defined as the sum of the weights of its edges. In this paper, we prove that: (1) if G is a 2‐connected weighted graph such that the minimum weighted degree of G is at least d, then for every given vertices x and y, either G contains a cycle of weight at least 2d passing through both of x and y or every heaviest cycle in G is a hamiltonian cycle, and (2) if G is a 2‐connected weighted graph such that the weighted degree sum of every pair of nonadjacent vertices is at least s, then for every vertex y, G contains either a cycle of weight at least s passing through y or a hamiltonian cycle. AMS classification: 05C45 05C38 05C35. © 2005 Wiley Periodicals, Inc. J Graph Theory     

The 2-hamiltonian cubes of graphs

This paper deals with the problem of characterizing the pairs of vertices x,y in a connected graph G such that G³ - {x,y} is hamiltonian, where G³ is the cube of G. It is known that the cube G³ is 2-hamiltonian if G is 2-connected. In this paper, we first prove the stronger result that G³ - {x,y} is hamiltonian if either x or y is not a cut-vertex of G, and then proceed to characterize those cut-vertices x and y of G such that G³ -{x,y} is hamiltonian. As a simple consequence of these, we obtain Schaar's characterization of a connected graph G such that G³ is 2-hamiltonian.     

Binding Number,Minimum Degree,and Cycle Structure in Graphs

A well‐known theorem of Woodall states that if a graph G has binding number at least 3/2, then G is hamiltonian. We generalize Woodall's theorem as follows.     

Prism‐hamiltonicity of triangulations

The prism over a graph G is the Cartesian product G □ K₂ of G with the complete graph K₂. If the prism over G is hamiltonian, we say that G is prism‐hamiltonian. We prove that triangulations of the plane, projective plane, torus, and Klein bottle are prism‐hamiltonian. We additionally show that every 4‐connected triangulation of a surface with sufficiently large representativity is prism‐hamiltonian, and that every 3‐connected planar bipartite graph is prism‐hamiltonian. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 181–197, 2008     

Closure Concepts: A Survey

In this paper we survey results of the following type (known as closure results). Let P be a graph property, and let C(u,v) be a condition on two nonadjacent vertices u and v of a graph G. Then G+uv has property P if and only if G has property P. The first and now well-known result of this type was established by Bondy and Chvátal in a paper published in 1976: If u and v are two nonadjacent vertices with degree sum n in a graph G on n vertices, then G+uv is hamiltonian if and only if G is hamiltonian. Based on this result, they defined the n-closure cl_n (G) of a graph G on n vertices as the graph obtained from G by recursively joining pairs of nonadjacent vertices with degree sum n until no such pair remains. They showed that cl_n(G) is well-defined, and that G is hamiltonian if and only if cl_n(G) is hamiltonian. Moreover, they showed that cl_n(G) can be obtained by a polynomial algorithm, and that a Hamilton cycle in cl_n(G) can be transformed into a Hamilton cycle of G by a polynomial algorithm. As a consequence, for any graph G with cl_n(G)=K _n (and n≥3), a Hamilton cycle can be found in polynomial time, whereas this problem is NP-hard for general graphs. All classic sufficient degree conditions for hamiltonicity imply a complete n-closure, so the closure result yields a common generalization as well as an easy proof for these conditions. In their first paper on closures, Bondy and Chvátal gave similar closure results based on degree sum conditions for nonadjacent vertices for other graph properties. Inspired by their first results, many authors developed other closure concepts for a variety of graph properties, or used closure techniques as a tool for obtaining deeper sufficiency results with respect to these properties. Our aim is to survey this progress on closures made in the past (more than) twenty years. Revised: September 27, 1999     

New constructions of hypohamiltonian and hypotraceable graphs

A graph G is hypohamiltonian/hypotraceable if it is not hamiltonian/traceable, but all vertex‐deleted subgraphs of G are hamiltonian/traceable. All known hypotraceable graphs are constructed using hypohamiltonian graphs; here we present a construction that uses so‐called almost hypohamiltonian graphs (nonhamiltonian graphs, whose vertex‐deleted subgraphs are hamiltonian with exactly one exception, see [15]). This construction is an extension of a method of Thomassen [11]. As an application, we construct a planar hypotraceable graph of order 138, improving the best‐known bound of 154 [8]. We also prove a structural type theorem showing that hypotraceable graphs possessing some connectivity properties are all built using either Thomassen's or our method. We also prove that if G is a Grinbergian graph without a triangular region, then G is not maximal nonhamiltonian and using the proof method we construct a hypohamiltonian graph of order 36 with crossing number 1, improving the best‐known bound of 46 [14].     

On Perfect Matching Coverings and Even Subgraph Coverings

A perfect matching covering of a graph G is a set of perfect matchings of G such that every edge of G is contained in at least one member of it. Berge conjectured that every bridgeless cubic graph admits a perfect matching covering of order at most 5 (we call such a collection of perfect matchings a Berge covering of G). A cubic graph G is called a Kotzig graph if G has a 3‐edge‐coloring such that each pair of colors forms a hamiltonian circuit (introduced by R. Häggkvist, K. Markström, J Combin Theory Ser B 96 (2006), 183–206). In this article, we prove that if there is a vertex w of a cubic graph G such that , the graph obtained from by suppressing all degree two vertices is a Kotzig graph, then G has a Berge covering. We also obtain some results concerning the so‐called 5‐even subgraph double cover conjecture.     

Circular colorings of weighted graphs

Suppose that G is a finite simple graph and w is a weight function which assigns to each vertex of G a nonnegative real number. Let C be a circle of length t. A t-circular coloring of (G, w) is a mapping Δ of the vertices of G to arcs of C such that Δ(x)∩Δ(y) = 0 if (x, y) ∈ E(G) and Δ(x) has length w(x). The circular-chromatic number of (G, w) is the least t for which there is a t-circular coloring of (G, w). This paper discusses basic properties of circular chromatic number of a weighted graph and relations between this parameter and other graph parameters. We are particularly interested in graphs G for which the circular-chromatic number of (G, w) is equal to the fractional clique weight of (G, w) for arbitrary weight function w. We call such graphs star-superperfect. We prove that odd cycles and their complements are star-superperfect. We then prove a theorem about the circular chromatic number of lexicographic product of graphs which provides a tool of constructing new star-superperfect graphs from old ones. © 1996 John Wiley & Sons, Inc.     

Hamiltonicity of regular 2-connected graphs

Let G be a k-regular 2-connected graph of order n. Jackson proved that G is hamiltonian if n ≤ 3k. Zhu and Li showed that the upper bound 3k on n can be relaxed to 22/7k if G is 3-connected and k ≥ 63. We improve both results by showing that G is hamiltonian if n ≤ 7/2k − 7 and G does not belong to a restricted class F of nonhamiltonian graphs of connectivity 2. To establish this result we obtain a variation of Woodall's Hopping Lemma and use it to prove that if n ≤ 7/2k − 7 and G has a dominating cycle (i.e., a cycle such that the vertices off the cycle constitute an independent set), then G is hamiltonian. We also prove that if n ≤ 4k − 3 and G ∉ F, then G has a dominating cycle. For k ≥ 4 it is conjectured that G is hamiltonian if n ≤ 4k and G ∉ F. © 1996 John Wiley & Sons, Inc.     

Degree conditions for k‐ordered hamiltonian graphs

For a positive integer k, a graph G is k-ordered hamiltonian if for every ordered sequence of k vertices there is a hamiltonian cycle that encounters the vertices of the sequence in the given order. It is shown that if G is a graph of order n with 3 ≤ k ≤ n/2, and deg(u) + deg(v) ≥ n + (3k − 9)/2 for every pair u, v of nonadjacent vertices of G, then G is k-ordered hamiltonian. Minimum degree conditions are also given for k-ordered hamiltonicity. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 199–210, 2003     

Edge disjoint cycles in graphs

Ore proved in 1960 that if G is a graph of order n and the sum of the degrees of any pair of nonadjacent vertices is at least n, then G has a hamiltonian cycle. In 1986, Li Hao and Zhu Yongjin showed that if n ? 20 and the minimum degree δ is at least 5, then the graph G above contains at least two edge disjoint hamiltonian cycles. The result of this paper is that if n ? 2δ², then for any 3 ? l₁ ? l₂ ? ? ? l_k ? n, 1 = k = [(δ - 1)/2], such graph has K edge disjoint cycles with lengths l₁, l₂…l_k, respectively. In particular, when l₁ = l₂ = ? = l_k = n and k = [(δ - 1)/2], the graph contains [(δ - 1)/2] edge disjoint hamiltonian cycles.     

Hamilton cycles in prisms

The prism over a graph G is the Cartesian product G □ K₂ of G with the complete graph K₂. If G is hamiltonian, then G□K₂ is also hamiltonian but the converse does not hold in general. Having a hamiltonian prism is shown to be an interesting relaxation of being hamiltonian. In this article, we examine classical problems on hamiltonicity of graphs in the context of having a hamiltonian prism. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 249–269, 2007     

Maximum Number of Contractible Edges on Hamiltonian Cycles of a 3-Connected Graph

 We show that if G is a 3-connected hamiltonian graph of order at least 5, then there exists a hamiltonian cycle C of G such that the number of contractible edges of G which are on C is greater than or equal to . Received: July 31, 2000 Final version received: December 12, 2000 Acknowledgments. I would like to thank Professor Yoshimi Egawa for the help he gave to me during the preparation of this paper.     

Hamiltonicity of 3-Arc Graphs

An arc of a graph is an oriented edge and a 3-arc is a 4-tuple (v, u, x, y) of vertices such that both (v, u, x) and (u, x, y) are paths of length two. The 3-arc graph of a graph G is defined to have vertices the arcs of G such that two arcs uv, xy are adjacent if and only if (v, u, x, y) is a 3-arc of G. We prove that any connected 3-arc graph is hamiltonian, and all iterative 3-arc graphs of any connected graph of minimum degree at least three are hamiltonian. As a corollary we obtain that any vertex-transitive graph which is isomorphic to the 3-arc graph of a connected arc-transitive graph of degree at least three must be hamiltonian. This confirms the conjecture, for this family of vertex-transitive graphs, that all vertex-transitive graphs with finitely many exceptions are hamiltonian. We also prove that if a graph with at least four vertices is Hamilton-connected, then so are its iterative 3-arc graphs.