Contractible Subgraphs,Thomassen's Conjecture and the Dominating Cycle Conjecture for Snarks

We show that the conjectures by Matthews and Sumner (every 4-connected claw-free graph is hamiltonian), by Thomassen (every 4-connected line graph is hamiltonian) and by Fleischner (every cyclically 4-edge-connected cubic graph has either a 3-edge-coloring or a dominating cycle), which are known to be equivalent, are equivalent with the statement that every snark (i.e. a cyclically 4-edge-connected cubic graph of girth at least five that is not 3-edge-colorable) has a dominating cycle.We use a refinement of the contractibility technique which was introduced by Ryjáček and Schelp in 2003 as a common generalization and strengthening of the reduction techniques by Catlin and Veldman and of the closure concept introduced by Ryjáček in 1997.     

A note about the dominating circuit conjecture

The dominating circuit conjecture states that every cyclically 4-edge-connected cubic graph has a dominating circuit. We show that this is equivalent to the statement that any two edges of such a cyclically 4-edge-connected graph are contained in a dominating circuit.     

Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs

The circumference of a graph is the length of its longest cycles. Results of Jackson, and Jackson and Wormald, imply that the circumference of a 3-connected cubic n-vertex graph is Ω(n^0.694), and the circumference of a 3-connected claw-free graph is Ω(n^0.121). We generalize and improve the first result by showing that every 3-edge-connected graph with m edges has an Eulerian subgraph with Ω(m^0.753) edges. We use this result together with the Ryjá?ek closure operation to improve the lower bound on the circumference of a 3-connected claw-free graph to Ω(n^0.753). Our proofs imply polynomial time algorithms for finding large Eulerian subgraphs of 3-edge-connected graphs and long cycles in 3-connected claw-free graphs.     

Closure, stability and iterated line graphs with a 2-factor

We consider 2-factors with a bounded number of components in the n-times iterated line graph Lⁿ(G). We first give a characterization of graph G such that Lⁿ(G) has a 2-factor containing at most k components, based on the existence of a certain type of subgraph in G. This generalizes the main result of [L. Xiong, Z. Liu, Hamiltonian iterated line graphs, Discrete Math. 256 (2002) 407-422]. We use this result to show that the minimum number of components of 2-factors in the iterated line graphs Lⁿ(G) is stable under the closure operation on a claw-free graph G. This extends results in [Z. Ryjá?ek, On a closure concept in claw-free graphs, J. Combin. Theory Ser. B 70 (1997) 217-224; Z. Ryjá?ek, A. Saito, R.H. Schelp, Closure, 2-factors and cycle coverings in claw-free graphs, J. Graph Theory 32 (1999) 109-117; L. Xiong, Z. Ryjá?ek, H.J. Broersma, On stability of the hamiltonian index under contractions and closures, J. Graph Theory 49 (2005) 104-115].     

Cycles through four edges in 3-connected cubic graphs

We give necessary and sufficient conditions for four edges in a 3-connected cubic graph to lie on a cycle. As a consequence, if such a graph is cyclically 4-edge-connected with order greater than 8 it is shown that any four independent edges lie on a cycle.     

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.     

Degree conditions on induced claws

We introduce a closure concept for a superclass of the class of claw-free graphs defined by a degree condition on end vertices of induced claws. We show that the closure of a graph is the line graph of a triangle-free graph, and that the closure operation preserves the length of a longest path and cycle. These results extend the closure concept for claw-free graphs introduced by Ryjá?ek.     

Matching theory and Barnette's conjecture

Barnette's Conjecture claims that all cubic, 3-connected, planar, bipartite graphs are Hamiltonian. We give a translation of this conjecture into the matching-theoretic setting. This allows us to relax the requirement of planarity to give the equivalent conjecture that all cubic, 3-connected, Pfaffian, bipartite graphs are Hamiltonian.A graph, other than the path of length three, is a brace if it is bipartite and any two disjoint edges are part of a perfect matching. Our perspective allows us to observe that Barnette's Conjecture can be reduced to cubic, planar braces. We show a similar reduction to braces for cubic, 3-connected, bipartite graphs regarding four stronger versions of Hamiltonicity. Note that in these cases we do not need planarity.As a practical application of these results, we provide some supplements to a generation procedure for cubic, 3-connected, planar, bipartite graphs discovered by Holton et al. (1985) [14]. These allow us to check whether a graph we generated is a brace.     

Non-hamiltonian 3-connected cubic bipartite graphs

A non-hamiltonian cyclically 4-edge-connected bicubic graph with 54 vertices is constructed. This is the smallest non-hamiltonian 3-connected bicubic graph known, and is the first such graph that is cyclically 4-edge-connected.     

A new closure concept preserving graph Hamiltonicity and based on neighborhood equivalence

A graph is Hamiltonian if it contains a cycle which goes through all vertices exactly once. Determining if a graph is Hamiltonian is known as an NP-complete problem, and no satisfactory characterization for these graphs has been found.In 1976, Bondy and Chvàtal introduced a way to get round the Hamiltonicity problem complexity by using a closure of the graph. This closure is a supergraph of G which is Hamiltonian iff G is. In particular, if the closure is the complete graph, then G is Hamiltonian. Since this seminal work, several closure concepts preserving Hamiltonicity have been introduced. In particular, in 1997, Ryjá?ek defined a closure concept for claw-free graphs based on local completion.Following a different approach, in 1974, Goodman and Hedetniemi gave a sufficient condition for Hamiltonicity based on the existence of a clique covering of the graph. This condition was recently generalized using the notion of Eulerian clique covering. In this context, closure concepts based on local completion are interesting since the closure of a graph contains more simplicial vertices than the graph itself, making the search for a clique covering easier.In this article, we introduce a new closure concept based on local completion which preserves the Hamiltonicity for every graph. Note that, moreover, the closure may be claw free even when the graph is not.     

On even cycle decompositions of line graphs of cubic graphs

An even cycle decomposition of a graph is a partition of its edges into cycles of even length. In 2012, Markström conjectured that the line graph of every 2-connected cubic graph has an even cycle decomposition and proved this conjecture for cubic graphs with oddness at most 2. However, for 2-connected cubic graphs with oddness 2, Markström only considered these graphs with a chordless 2-factor. (A chordless 2-factor of a graph is a 2-factor consisting of only induced cycles.) In this paper, we first construct an infinite family of 2-connected cubic graphs with oddness 2 and without chordless 2-factors. We then give a complete proof of Markström’s result and further prove this conjecture for cubic graphs with oddness 4.     

Uniquely Edge-3-Colorable Graphs and Snarks

 A cubic graph G is uniquely edge-3-colorable if G has precisely one 1-factorization. It is proved in this paper, if a uniquely edge-3-colorable, cubic graph G is cyclically 4-edge-connected, but not cyclically 5-edge-connected, then G must contain a snark as a minor. This is an approach to a conjecture that every triangle free uniquely edge-3-colorable cubic graph must have the Petersen graph as a minor. Fiorini and Wilson (1976) conjectured that every uniquely edge-3-colorable planar cubic graph must have a triangle. It is proved in this paper that every counterexample to this conjecture is cyclically 5-edge-connected and that in a minimal counterexample to the conjecture, every cyclic 5-edge-cut is trivial (an edge-cut T of G is cyclic if no component of G\T is acyclic and a cyclic edge-cut T is trivial if one component of G\T is a circuit of length |T|). Received: July 14, 1997 Revised: June 11, 1998     

A note on Barnette’s conjecture

A well-known conjecture of Barnette states that every 3-connected cubic bipartite planar graph has a Hamiltonian cycle, which is equivalent to the statement that every 3-connected even plane triangulation admits a 2-tree coloring, meaning that the vertices of the graph have a 2-coloring such that each color class induces a tree. In this paper we present a new approach to Barnette’s conjecture by using 2-tree coloring.A Barnette triangulation is a 3-connected even plane triangulation, and a B-graph is a smallest Barnette triangulation without a 2-tree coloring. A configuration is reducible if it cannot be a configuration of a B-graph. We prove that certain configurations are reducible. We also define extendable, non-extendable and compatible graphs; and discuss their connection with Barnette’s conjecture.     

Graphs and digraphs with all 2-factors isomorphic

We show that a digraph which contains a directed 2-factor and has minimum in-degree and out-degree at least four has two non-isomorphic directed 2-factors. As a corollary, we deduce that every graph which contains a 2-factor and has minimum degree at least eight has two non-isomorphic 2-factors. In addition we construct: an infinite family of 3-diregular digraphs with the property that all their directed 2-factors are Hamilton cycles, an infinite family of 2-connected 4-regular graphs with the property that all their 2-factors are isomorphic, and an infinite family of cyclically 6-edge-connected cubic graphs with the property that all their 2-factors are Hamilton cycles.     

Removable edges in cyclically 4-edge-connected cubic graphs

We consider various ways of obtaining smaller cyclically 4-edge-connected cubic graphs from a given such graph. In particular, we consider removable edges: an edgee of a cyclically 4-edge-connected cubic graphG is said to be removable ifG is also cyclically 4-edge-connected, whereG is the cubic graph obtained fromG by deletinge and suppressing the two vertices of degree 2 created by the deletion. We prove that any cyclically 4-edge-connected cubic graphG with at least 12 vertices has at least 1/5(|E(G)| + 12) removable edges, and we characterize the graphs with exactly 1/5(|E(G)| + 12) removable edges.This work was carried out while the first author held a Niels Bohr Fellowship from the Royal Danish Academy of Sciences.     

On some structural properties of generalized fullerene graphs with 13 pentagonal faces

It is shown that every generalized fullerene graph G with 13 pentagons is 2-extendable, a brick, and cyclically 5-edge-connected, i.e., that G cannot be separated into two components, each containing a cycle, by deletion of fewer than five edges. New lower bound on the number of perfect matchings in such graphs are also established.     

Cycles with Prescribed and Forbidden Sets of Elements in Cubic Graphs

 A necessary and sufficient condition for the existence of a cycle containing a set of three vertices and an edge excluding another edge is obtained for 3-connected cubic graphs by means of canonical contractions. A necessary and sufficient condition is also obtained for a cyclically 4-connected cubic graph to have a cycle that contains a set of four vertices and that avoids another vertex. Received: October 4, 1999 Final version received: June 14, 2000     

Every 3-connected essentially 10-connected line graph is Hamilton-connected

Thomassen conjectured that every 4-connected line graph is Hamiltonian. Lai et al. (in 2006) [5] considered whether the high essential connectivity of the 3-connected line graphs can guarantee the existence of the Hamiltonian cycle in graphs and they showed that every 3-connected, essentially 11-connected line graph is Hamiltonian. In this note, we show that every 3-connected, essentially 10-connected line graph is Hamiltonian-connected. The result strengthens the known result mentioned above.     

3-连通3-正则图中的可序子集

图G的k元点集X={x1,x2,…,xk}被称为G的k-可序子集,如果X的任意排列都按序排在G的某个圈上.称G是k-可序图,如果G的每一个k元子集都是G的k-可序子集.称G为k-可序Hamilton图,如果X的任意排列都位于G的Hamilton圈上.研究了3-连通3-正则图的可序子集的存在性问题.     

On cyclic edge-connectivity of fullerenes

A graph is said to be cyclically k-edge-connected, if at least k edges must be removed to disconnect it into two components, each containing a cycle. Such a set of k edges is called a cyclic-k-edge cutset and it is called a trivial cyclic-k-edge cutset if at least one of the resulting two components induces a single k-cycle.It is known that fullerenes, that is, 3-connected cubic planar graphs all of whose faces are pentagons and hexagons, are cyclically 5-edge-connected. In this article it is shown that a fullerene F containing a nontrivial cyclic-5-edge cutset admits two antipodal pentacaps, that is, two antipodal pentagonal faces whose neighboring faces are also pentagonal. Moreover, it is shown that F has a Hamilton cycle, and as a consequence at least 15·2^n/20-1/2 perfect matchings, where n is the order of F.