Cycle double covers and the semi-Kotzig frame

Let H be a cubic graph admitting a 3-edge-coloring c:E(H)→Z₃ such that the edges colored with 0 and μ∈{1,2} induce a Hamilton circuit of H and the edges colored with 1 and 2 induce a 2-factor F. The graph H is semi-Kotzig if switching colors of edges in any even subgraph of F yields a new 3-edge-coloring of H having the same property as c. A spanning subgraph H of a cubic graph G is called a semi-Kotzig frame if the contracted graph G/H is even and every non-circuit component of H is a subdivision of a semi-Kotzig graph.In this paper, we show that a cubic graph G has a circuit double cover if it has a semi-Kotzig frame with at most one non-circuit component. Our result generalizes some results of Goddyn [L.A. Goddyn, Cycle covers of graphs, Ph.D. Thesis, University of Waterloo, 1988], and Häggkvist and Markström [R. Häggkvist, K. Markström, Cycle double covers and spanning minors I, J. Combin. Theory Ser. B 96 (2006) 183-206].     

Splits of circuits

This paper discusses an attempt at identifying a property of circuits in (nonplanar) graphs resembling the separation property of circuits in planar graphs derived from the Jordan Curve Theorem.If G is a graph and C is a circuit in G, we say that two circuits in G form a split of C if the symmetric difference of their edges sets is equal to the edge set of C, and if they are separated in G by the intersection of their vertex sets.García Moreno and Jensen, A note on semiextensions of stable circuits, Discrete Math. 309 (2009) 4952-4954, asked whether such a split exists for any circuit C whenever G is 3-connected. We observe that if true, this implies a strong form of a version of the Cycle Double-Cover Conjecture suggested in the Ph.D. thesis of Luis Goddyn. The main result of the paper shows that the property holds for Hamilton circuits in cubic graphs.     

Reduced graphs of diameter two

A graph H is collapsible if for every subset X ? V(H), H has a spanning connected subgraph whose set of odd-degree vertices is X. In any graph G there is a unique collection of maximal collapsible subgraphs, and when all of them are contracted, the resulting contraction of G is a reduced graph. Interest in reduced graphs arises from the fact [4] that a graph G has a spanning closed trail if and only if its corresponding reduced graph has a spanning closed trail. The concept can also be applied to study hamiltonian line graphs [11] or double cycle covers [8]. In this article, we characterize the reduced graphs of diameter two. As applications, we obtain prior results in [12] and [14], and show that every 2-edge-connected graph with diameter at most two either admits a double cycle cover with three even subgraphs or is isomorphic to the Petersen graph.     

Circuit double covers in special types of cubic graphs

Suppose that a 2-connected cubic graph G of order n has a circuit C of length at least n−4 such that G−V(C) is connected. We show that G has a circuit double cover containing a prescribed set of circuits which satisfy certain conditions. It follows that hypohamiltonian cubic graphs (i.e., non-hamiltonian cubic graphs G such that G−v is hamiltonian for every v∈V(G)) have strong circuit double covers.     

Even subgraphs of bridgeless graphs and 2-factors of line graphs

By Petersen's theorem, a bridgeless cubic multigraph has a 2-factor. Fleischner generalised this result to bridgeless multigraphs of minimum degree at least three by showing that every such multigraph has a spanning even subgraph. Our main result is that every bridgeless simple graph with minimum degree at least three has a spanning even subgraph in which every component has at least four vertices. We deduce that if G is a simple bridgeless graph with n vertices and minimum degree at least three, then its line graph has a 2-factor with at most max{1,(3n-4)/10} components. This upper bound is best possible.     

A characterization of Hamiltonian prisms

A characterization is established for a graph G to have a Hamilton cycle in G × K₂, the prism over G. Moreover, it is shown that every 3-connected graph has a 2-connected spanning bipartite subgraph. Using this result, the existence of a Hamilton cycle in the prism over every 3-connected cubic graph is established. Further, the existence of a Hamilton cycle in the prism over a cubic 2-connected graph is also discussed. Earlier results in this direction are shown to be particular cases of the results obtained here. © 1993 John Wiley & Sons, Inc.     

A bound on the total size of a cut cover

A cycle cover (cut cover) of a graph G is a collection of cycles (cuts) of G that covers every edge of G at least once. The total size of a cycle cover (cut cover) is the sum of the number of edges of the cycles (cuts) in the cover.We discuss several results for cycle covers and the corresponding results for cut covers. Our main result is that every connected graph on n vertices and e edges has a cut cover of total size at most 2e-n+1 with equality precisely when every block of the graph is an odd cycle or a complete graph (other than K₄ or K₈). This corresponds to the result of Fan [J. Combin. Theory Ser. B 74 (1998) 353-367] that every graph without cut-edges has a cycle cover of total size at most e+n-1.     

Critical groups of graphs with reflective symmetry

The critical group of a graph is a finite Abelian group whose order is the number of spanning forests of the graph. For a graph G with a certain reflective symmetry, we generalize a result of Ciucu–Yan–Zhang factorizing the spanning tree number of G by interpreting this as a result about the critical group of G. Our result takes the form of an exact sequence, and explicit connections to bicycle spaces are made.     

Supereulerian graphs and the Petersen graph

A graphG is supereulerian if G has a spanning eulerian subgraph.Boesch et al.[J.Graph Theory,1,79–84(1977)]proposed the problem of characterizing supereulerian graphs.In this paper,we prove that any 3-edge-connected graph with at most 11 edge-cuts of size 3 is supereulerian if and only if it cannot be contractible to the Petersen graph.This extends a former result of Catlin and Lai[J.Combin.Theory,Ser.B,66,123–139(1996)].     

Cycle Double Covers in Cubic Graphs having Special Structures

In the first part of this article, we employ Thomason's Lollipop Lemma 25 to prove that bridgeless cubic graphs containing a spanning lollipop admit a cycle double cover (CDC) containing the circuit in the lollipop; this implies, in particular, that bridgeless cubic graphs with a 2‐factor F having two components admit CDCs containing any of the components in the 2‐factor, although it need not have a CDC containing all of F. As another example consider a cubic bridgeless graph containing a 2‐factor with three components, all induced circuits. In this case, two of the components may separately be used to start a CDC although it is uncertain whether the third component may be part of some CDC. Numerous other corollaries shall be given as well. In the second part of the article, we consider special types of bridgeless cubic graphs for which a prominent circuit can be shown to be included in a CDC. The interest here is the proof technique and therefore we only give the simplest case of the theorem. Notably, we show that a cubic graph that consists of an induced 2k‐circuit C together with an induced 4k‐circuit T and an independent set of 2k vertices, each joined by one edge to C and two edges to T, has a CDC starting with T.     

Forcing faces in plane bipartite graphs

Let Ω denote the class of connected plane bipartite graphs with no pendant edges. A finite face s of a graph G∈Ω is said to be a forcing face of G if the subgraph of G obtained by deleting all vertices of s together with their incident edges has exactly one perfect matching. This is a natural generalization of the concept of forcing hexagons in a hexagonal system introduced in Che and Chen [Forcing hexagons in hexagonal systems, MATCH Commun. Math. Comput. Chem. 56 (3) (2006) 649-668]. We prove that any connected plane bipartite graph with a forcing face is elementary. We also show that for any integers n and k with n?4 and n?k?0, there exists a plane elementary bipartite graph such that exactly k of the n finite faces of G are forcing. We then give a shorter proof for a recent result that a connected cubic plane bipartite graph G has at least two disjoint M-resonant faces for any perfect matching M of G, which is a main theorem in the paper [S. Bau, M.A. Henning, Matching transformation graphs of cubic bipartite plane graphs, Discrete Math. 262 (2003) 27-36]. As a corollary, any connected cubic plane bipartite graph has no forcing faces. Using the tool of Z-transformation graphs developed by Zhang et al. [Z-transformation graphs of perfect matchings of hexagonal systems, Discrete Math. 72 (1988) 405-415; Plane elementary bipartite graphs, Discrete Appl. Math. 105 (2000) 291-311], we characterize the plane elementary bipartite graphs whose finite faces are all forcing. We also obtain a necessary and sufficient condition for a finite face in a plane elementary bipartite graph to be forcing, which enables us to investigate the relationship between the existence of a forcing edge and the existence of a forcing face in a plane elementary bipartite graph, and find out that the former implies the latter but not vice versa. Moreover, we characterize the plane bipartite graphs that can be turned to have all finite faces forcing by subdivisions.     

Some results on the incidence coloring number of a graph

This paper proves that if G is a cubic graph which has a Hamiltonian path or G is a bridgeless cubic graph of large girth, then its incidence coloring number is at most 5. By relating the incidence coloring number of a graph G to the chromatic number of G², we present simple proofs of some known results, and characterize regular graphs G whose incidence coloring number equals Δ(G)+1.     

Even polyhedral decompositions of cubic graphs

An even polyhedral decomposition of a finite cubic graph G is defined as a set of elementary cycles of even length in G with the property that each edge of G lies in exactly two of them. If G has chromatic index three, then G has an even polyhedral decomposition. We show that, contrary to a theorem of Szekkeres [2], this property to have an even polyhedral decomposition doesn't characterize the cubic graphs of chromatic index three. In particular, there exists an infinite family of sharks all having an even polyhedral decomposition.     

Oriented walk double covering and bidirectional double tracing

An oriented walk double covering of a graph G is a set of oriented closed walks, that, traversed successively, combined will have traced each edge of G once in each direction. A bidirectional double tracing of a graph G is an oriented walk double covering that consists of a single closed walk. A retracting in a closed walk is the immediate succession of an edge by its inverse. Every graph with minimum degree 2 has a retracting free oriented walk double covering and every connected graph has a bidirectional double tracing. The minimum number of closed walks in a retracting free oriented walk double covering of G is denoted by c(G). The minimum number of retractings in a bidirectional double tracing of G is denoted by r(G). We shall prove that for all connected noncycle graphs G with minimum degree at least 2, r(G) = c(G) − 1. The problem of characterizing those graphs G for which r(G) = 0 was raised by Ore. Thomassen solved this problem by relating it to the existence of certain spanning trees. We generalize this result, and relate the parameters r(G), c(G) to spanning trees of G. This relation yields a polynomial time algorithm to determine the parameters c(G) and r(G). © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 89–102, 1998     

Enumerating spanning trees of graphs with an involution

As the extension of the previous work by Ciucu and the present authors [M. Ciucu, W.G. Yan, F.J. Zhang, The number of spanning trees of plane graphs with reflective symmetry, J. Combin. Theory Ser. A 112 (2005) 105-116], this paper considers the problem of enumeration of spanning trees of weighted graphs with an involution which allows fixed points. We show that if G is a weighted graph with an involution, then the sum of weights of spanning trees of G can be expressed in terms of the product of the sums of weights of spanning trees of two weighted graphs with a smaller size determined by the involution of G. As applications, we enumerate spanning trees of the almost-complete bipartite graph, the almost-complete graph, the Möbius ladder, and the almost-join of two copies of a graph.     

Flows, flow-pair covers and cycle double covers

In this paper, some earlier results by Fleischner [H. Fleischner, Bipartizing matchings and Sabidussi’s compatibility conjecture, Discrete Math. 244 (2002) 77-82] about edge-disjoint bipartizing matchings of a cubic graph with a dominating circuit are generalized for graphs without the assumption of the existence of a dominating circuit and 3-regularity. A pair of integer flows (D,f₁) and (D,f₂) is an (h,k)-flow parity-pair-cover of G if the union of their supports covers the entire graph; f₁ is an h-flow and f₂ is a k-flow, and . Then G admits a nowhere-zero 6-flow if and only if G admits a (4,3)-flow parity-pair-cover; and G admits a nowhere-zero 5-flow if G admits a (3,3)-flow parity-pair-cover. A pair of integer flows (D,f₁) and (D,f₂) is an (h,k)-flow even-disjoint-pair-cover of G if the union of their supports covers the entire graph, f₁ is an h-flow and f₂ is a k-flow, and for each {i,j}={1,2}. Then G has a 5-cycle double cover if G admits a (4,4)-flow even-disjoint-pair-cover; and G admits a (3,3)-flow parity-pair-cover if G has an orientable 5-cycle double cover.     

Edge covering coloring of nearly bipartite graphs

LetG be a simple graph with vertex setV(G) and edge setE(G). A subsetS ofE(G) is called an edge cover ofG if the subgraph induced byS is a spanning subgraph ofG. The maximum number of edge covers which form a partition ofE(G) is called edge covering chromatic number ofG, denoted by χ′_c(G). It known that for any graphG with minimum degreeδ,δ -1 ≤χ′_c(G) ≤δ. If χ′_c(G) =δ, thenG is called a graph of CI class, otherwiseG is called a graph of CII class. It is easy to prove that the problem of deciding whether a given graph is of CI class or CII class is NP-complete. In this paper, we consider the classification of nearly bipartite graph and give some sufficient conditions for a nearly bipartite graph to be of CI class.     

Graph factors and factorization: 1985–2003: A survey

In the most general sense, a factor of a graph G is just a spanning subgraph of G and a graph factorization of G is a partition of the edges of G into factors. However, as we shall see in the present paper, even this extremely general definition does not capture all the factor and factorization problems that have been studied in graph theory. Several previous survey papers have been written on this subject [F. Chung, R. Graham, Recent results in graph decompositions, London Mathematical Society, Lecture Note Series, vol. 52, Cambridge University Press, 1981, pp. 103–123; J. Akiyama, M. Kano, Factors and factorizations of graphs—a survey, J. Graph Theory 9 (1985) 1–42; L. Volkmann, Regular graphs, regular factors, and the impact of Petersen's theorems, Jahresber. Deutsch. Math.-Verein. 97 (1995) 19–42] as well as an entire book on graph decompositions [J. Bosák, Decompositions of Graphs, Kluwer Academic Publishers Group, Dordrecht, 1990]. Our purpose here is to concentrate primarily on surveying the developments of the last 15–20 years in this exponentially growing field.     

A Note on 5-Cycle Double Covers

The strong cycle double cover conjecture states that for every circuit C of a bridgeless cubic graph G, there is a cycle double cover of G which contains C. We conjecture that there is even a 5-cycle double cover S of G which contains C, i.e. C is a subgraph of one of the five 2-regular subgraphs of S. We prove a necessary and sufficient condition for a 2-regular subgraph to be contained in a 5-cycle double cover of G.     

Snarks,Hypohamiltonian Graphs and Non-Supereulerian Graphs

A graph G is hypohamiltonian if it is not Hamiltonian but for each \(v\in V(G)\), the graph \(G-v\) is Hamiltonian. A graph is supereulerian if it has a spanning Eulerian subgraph. A graph G is called collapsible if for every even subset \(R\subseteq V(G)\), there is a spanning connected subgraph H of G such that R is the set of vertices of odd degree in H. A graph is reduced if it has no nontrivial collapsible subgraphs. In this note, we first prove that all hypohamiltonian cubic graphs are reduced non-supereulerian graphs. Then we introduce an operation to construct graphs from hypohamiltonian cubic graphs such that the resulting graphs are 3-edge-connected non-supereulerian reduced graphs and cannot be contracted to a snark. This disproves two conjectures, one of which was first posed by Catlin et al. in [Congr. Num. 76:173–181, 1990] and in [J. Combin. Theory, Ser B 66:123–139, 1996], and was posed again by Li et al. in [Acta Math. Sin. English Ser 30(2):291–304, 2014] and by Yang in [Supereulerian graphs, hamiltonicity of graphs and several extremal problems in graphs, Ph. D. Dissertation, Université Paris-Sub, September 27, 2013], respectively, the other one was posed by Yang 2013.