Thomassen's conjecture implies polynomiality of 1‐Hamilton‐connectedness in line graphs

A graph G is 1‐Hamilton‐connected if G?x is Hamilton‐connected for every x∈V(G), and G is 2‐edge‐Hamilton‐connected if the graph G+ X has a hamiltonian cycle containing all edges of X for any X?E⁺(G) = {xy| x, y∈V(G)} with 1≤|X|≤2. We prove that Thomassen's conjecture (every 4‐connected line graph is hamiltonian, or, equivalently, every snark has a dominating cycle) is equivalent to the statements that every 4‐connected line graph is 1‐Hamilton‐connected and/or 2‐edge‐Hamilton‐connected. As a corollary, we obtain that Thomassen's conjecture implies polynomiality of both 1‐Hamilton‐connectedness and 2‐edge‐Hamilton‐connectedness in line graphs. Consequently, proving that 1‐Hamilton‐connectedness is NP‐complete in line graphs would disprove Thomassen's conjecture, unless P = NP. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 241–250, 2012     

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     

Claw‐free 3‐connected P11‐free graphs are hamiltonian

We show that every 3‐connected claw‐free graph which contains no induced copy of P₁₁ is hamiltonian. Since there exist non‐hamiltonian 3‐connected claw‐free graphs without induced copies of P₁₂ this result is, in a way, best possible. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 111–121, 2004     

Hamiltonicity and forbidden subgraphs in 4‐connected graphs

Let T be the line graph of the unique tree F on 8 vertices with degree sequence (3,3,3,1,1,1,1,1), i.e., T is a chain of three triangles. We show that every 4‐connected {T, K_1,3}‐free graph has a hamiltonian cycle. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 262–272, 2005     

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     

2‐ and 3‐factors of graphs on surfaces

It has been conjectured that any 5‐connected graph embedded in a surface Σ with sufficiently large face‐width is hamiltonian. This conjecture was verified by Yu for the triangulation case, but it is still open in general. The conjecture is not true for 4‐connected graphs. In this article, we shall study the existence of 2‐ and 3‐factors in a graph embedded in a surface Σ. A hamiltonian cycle is a special case of a 2‐factor. Thus, it is quite natural to consider the existence of these factors. We give an evidence to the conjecture in a sense of the existence of a 2‐factor. In fact, we only need the 4‐connectivity with minimum degree at least 5. In addition, our face‐width condition is not huge. Specifically, we prove the following two results. Let G be a graph embedded in a surface Σ of Euler genus g.

• (1) If G is 4‐connected and minimum degree of G is at least 5, and furthermore, face‐width of G is at least 4g?12, then G has a 2‐factor.
• (2) If G is 5‐connected and face‐width of G is at least max{44g?117, 5}, then G has a 3‐factor.

The connectivity condition for both results are best possible. In addition, the face‐width conditions are necessary too. Copyright © 2010 Wiley Periodicals, Inc. J Graph Theory 67:306‐315, 2011     

On the hamiltonicity of line graphs of locally finite, 6‐edge‐connected graphs

The topological approach to the study of infinite graphs of Diestel and KÜhn has enabled several results on Hamilton cycles in finite graphs to be extended to locally finite graphs. We consider the result that the line graph of a finite 4‐edge‐connected graph is hamiltonian. We prove a weaker version of this result for infinite graphs: The line graph of locally finite, 6‐edge‐connected graph with a finite number of ends, each of which is thin, is hamiltonian.     

4‐Coloring P6‐Free Graphs with No Induced 5‐Cycles

We show that the 4‐coloring problem can be solved in polynomial time for graphs with no induced 5‐cycle C₅ and no induced 6‐vertex path P₆     

Enclosings of λ‐Fold 5‐Cycle Systems: Adding One Vertex

A k‐cycle system of a multigraph G is an ordered pair (V, C) where V is the vertex set of G and C is a set of k‐cycles, the edges of which partition the edges of G. A k‐cycle system of is known as a λ‐fold k‐cycle system of order V. A k‐cycle system of (V, C) is said to be enclosed in a k‐cycle system of if and . We settle the difficult enclosing problem for λ‐fold 5‐cycle systems with u = 1.     

1‐rotationally resolvable 4‐cycle systems of 2Kv

In this article, it is shown that there exists a 1‐rotationally resolvable 4‐cycle system of 2K_υ if and only if υ ≡ 0 (mod 4). To prove that, some special sequences of integers are utilized. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 116–125, 2002; DOI 10.1002/jcd.10006     

Line graphs of multigraphs and Hamilton‐connectedness of claw‐free graphs

We introduce a closure concept that turns a claw‐free graph into the line graph of a multigraph while preserving its (non‐)Hamilton‐connectedness. As an application, we show that every 7‐connected claw‐free graph is Hamilton‐connected, and we show that the well‐known conjecture by Matthews and Sumner (every 4‐connected claw‐free graph is hamiltonian) is equivalent with the statement that every 4‐connected claw‐free graph is Hamilton‐connected. Finally, we show a natural way to avoid the non‐uniqueness of a preimage of a line graph of a multigraph, and we prove that the closure operation is, in a sense, best possible. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:152‐173, 2011     

Orthogonal double covers by super‐extendable cycles

An Orthogonal Double Cover (ODC) of the complete graph K_n by an almost‐hamiltonian cycle is a decomposition of 2K_n into cycles of length n?1 such that the intersection of any two of them is exactly one edge. We introduce a new class of such decompositions. If n is a prime, the special structure of such a decomposition allows to expand it to an ODC of K_n+1 by an almost‐hamiltonian cycle. This yields the existence of an ODC of K_p+1 by an almost‐hamiltonian cycle for primes p of order 3 mod 4 and its eventual existence for arbitrary primes p. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 283–293, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10011     

A Closure for 1‐Hamilton‐Connectedness in Claw‐Free Graphs

A graph G is 1‐Hamilton‐connected if is Hamilton‐connected for every vertex . In the article, we introduce a closure concept for 1‐Hamilton‐connectedness in claw‐free graphs. If is a (new) closure of a claw‐free graph G, then is 1‐Hamilton‐connected if and only if G is 1‐Hamilton‐connected, is the line graph of a multigraph, and for some , is the line graph of a multigraph with at most two triangles or at most one double edge. As applications, we prove that Thomassen's Conjecture (every 4‐connected line graph is hamiltonian) is equivalent to the statement that every 4‐connected claw‐free graph is 1‐Hamilton‐connected, and we present results showing that every 5‐connected claw‐free graph with minimum degree at least 6 is 1‐Hamilton‐connected and that every 4‐connected claw‐free and hourglass‐free graph is 1‐Hamilton‐connected.     

Maximal K3's and Hamiltonicity of 4‐connected claw‐free graphs

Let cl(G) denote Ryjá?ek's closure of a claw‐free graph G. In this article, we prove the following result. Let G be a 4‐connected claw‐free graph. Assume that G[N_G(T)] is cyclically 3‐connected if T is a maximal K₃ in G which is also maximal in cl(G). Then G is hamiltonian. This result is a common generalization of Kaiser et al.'s theorem [J Graph Theory 48(4) (2005), 267–276] and Pfender's theorem [J Graph Theory 49(4) (2005), 262–272]. © 2011 Wiley Periodicals, Inc. J Graph Theory     

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.     

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     

Perfect 1‐Factorizations of a Family of Cayley Graphs

A 1‐factorization of a graph G is a decomposition of G into edge‐disjoint 1‐factors (perfect matchings), and a perfect 1‐factorization is a 1‐factorization in which the union of any two of the 1‐factors is a Hamilton cycle. We consider the problem of the existence of perfect 1‐factorizations of even order 4‐regular Cayley graphs, with a particular interest in circulant graphs. In this paper, we study a new family of graphs, denoted , which are Cayley graphs if and only if k is even or . By solving the perfect 1‐factorization problem for a large class of graphs, we obtain a new class of 4‐regular bipartite circulant graphs that do not have a perfect 1‐factorization, answering a problem posed in 7 . With further study of graphs, we prove the nonexistence of P1Fs in a class of 4‐regular non‐bipartite circulant graphs, which is further support for a conjecture made in 7 .     

Arc‐Disjoint Cycles and Feedback Arc Sets

Isaak posed the following problem. Suppose T is a tournament having a minimum feedback arc set, which induces an acyclic digraph with a hamiltonian path. Is it true that the maximum number of arc‐disjoint cycles in T equals the cardinality of minimum feedback arc set of T? We prove that the answer to the problem is in the negative.     

Cycles and paths in edge‐colored graphs with given degrees

Sufficient degree conditions for the existence of properly edge‐colored cycles and paths in edge‐colored graphs, multigraphs and random graphs are investigated. In particular, we prove that an edge‐colored multigraph of order n on at least three colors and with minimum colored degree greater than or equal to ?(n+1)/2? has properly edge‐colored cycles of all possible lengths, including hamiltonian cycles. Longest properly edge‐colored paths and hamiltonian paths between given vertices are considered as well. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 63–86, 2010     

On Toughness and Hamiltonicity of 2K2‐Free Graphs

The toughness of a (noncomplete) graph G is the minimum value of t for which there is a vertex cut A whose removal yields components. Determining toughness is an NP‐hard problem for general input graphs. The toughness conjecture of Chvátal, which states that there exists a constant t such that every graph on at least three vertices with toughness at least t is hamiltonian, is still open for general graphs. We extend some known toughness results for split graphs to the more general class of 2K₂‐free graphs, that is, graphs that do not contain two vertex‐disjoint edges as an induced subgraph. We prove that the problem of determining toughness is polynomially solvable and that Chvátal's toughness conjecture is true for 2K₂‐free graphs.