On 2-factor hamiltonian regular bipartite graphs

A k-regular bipartite graph is said to be 2-factor hamiltonian if each of its 2-factor is hamiltonian. It is well known that if a k-regular bipartite graph is 2-factor hamiltonian, then k?Q3. In this paper, we give a new proof of this fact.     

Acyclic edge coloring of planar graphs without cycles of?specific lengths

A proper edge coloring of a graph G is called acyclic edge coloring if there are no bicolored cycles in G. Let ??(G) denote the maximum degree of G. In this paper, we prove that every planar graph with ??(G)??10 and without cycles of lengths 4 to 11 is acyclic (??(G)+1)-edge colorable, and every planar graph with ??(G)??11 and without cycles of lengths 4 to 9 is acyclic (??(G)+1)-edge colorable.     

Characterization of reducible hexagons and fast decomposition of elementary benzenoid graphs

A benzenoid graph is a finite connected plane graph with no cut vertices in which every interior region is bounded by a regular hexagon of a side length one. A benzenoid graph G is elementary if every edge belongs to a 1-factor of G. A hexagon h of an elementary benzenoid graph is reducible, if the removal of boundary edges and vertices of h results in an elementary benzenoid graph. We characterize the reducible hexagons of an elementary benzenoid graph. The characterization is the basis for an algorithm which finds the sequence of reducible hexagons that decompose a graph of this class in O(n²) time. Moreover, we present an algorithm which decomposes an elementary benzenoid graph with at most one pericondensed component in linear time.     

Algorithmic proofs of two relations between connectivity and the 1-factors of a graph

An algorithm is used to give simple proofs of these two known relations in the theory of matched graphs: A graph with a unique 1-factor contains a matched bridge; an n-connected graph with a 1-factor has at least n totally covered vertices, if n?2. Conditions for exactly n, or more than n, totally covered vertices are also given.     

Path factors and parallel knock-out schemes of almost claw-free graphs

An H₁,{H₂}-factor of a graph G is a spanning subgraph of G with exactly one component isomorphic to the graph H₁ and all other components (if there are any) isomorphic to the graph H₂. We completely characterise the class of connected almost claw-free graphs that have a P₇,{P₂}-factor, where P₇ and P₂ denote the paths on seven and two vertices, respectively. We apply this result to parallel knock-out schemes for almost claw-free graphs. These schemes proceed in rounds in each of which each surviving vertex eliminates one of its surviving neighbours. A graph is reducible if such a scheme eliminates every vertex in the graph. Using our characterisation, we are able to classify all reducible almost claw-free graphs, and we can show that every reducible almost claw-free graph is reducible in at most two rounds. This leads to a quadratic time algorithm for determining if an almost claw-free graph is reducible (which is a generalisation and improvement upon the previous strongest result that showed that there was a O(n^5.376) time algorithm for claw-free graphs on n vertices).     

Hamilton decompositions of graphs with primitive complements

A k-factor of a graph is a k-regular spanning subgraph. A Hamilton cycle is a connected 2-factor. A graph G is said to be primitive if it contains no k-factor with 1≤k<Δ(G). A Hamilton decomposition of a graph G is a partition of the edges of G into sets, each of which induces a Hamilton cycle. In this paper, by using the amalgamation technique, we find necessary and sufficient conditions for the existence of a 2x-regular graph G on n vertices which:

1.

has a Hamilton decomposition, and

2.

has a complement in K_n that is primitive.

This extends the conditions studied by Hoffman, Rodger, and Rosa [D.G. Hoffman, C.A. Rodger, A. Rosa, Maximal sets of 2-factors and Hamiltonian cycles, J. Combin. Theory Ser. B 57 (1) (1993) 69-76] who considered maximal sets of Hamilton cycles and 2-factors. It also sheds light on construction approaches to the Hamilton-Waterloo problem.     

Irreducible pseudo 2-factor isomorphic cubic bipartite graphs

A bipartite graph is pseudo 2-factor isomorphic if the number of circuits in each 2-factor of the graph is always even or always odd. We proved (Abreu et?al., J Comb Theory B 98:432–442, 2008) that the only essentially 4-edge-connected pseudo 2-factor isomorphic cubic bipartite graph of girth 4 is K _3,3, and conjectured (Abreu et?al., 2008, Conjecture 3.6) that the only essentially 4-edge-connected cubic bipartite graphs are K _3,3, the Heawood graph and the Pappus graph. There exists a characterization of symmetric configurations n ₃ due to Martinetti (1886) in which all symmetric configurations n ₃ can be obtained from an infinite set of so called irreducible configurations (Martinetti, Annali di Matematica Pura ed Applicata II 15:1–26, 1888). The list of irreducible configurations has been completed by Boben (Discret Math 307:331–344, 2007) in terms of their irreducible Levi graphs. In this paper we characterize irreducible pseudo 2-factor isomorphic cubic bipartite graphs proving that the only pseudo 2-factor isomorphic irreducible Levi graphs are the Heawood and Pappus graphs. Moreover, the obtained characterization allows us to partially prove the above Conjecture.     

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.     

Characterization of self-complementary graphs with 2-factors

Let G be a self-complementary graph (s.c.) and π its degree sequence. Then G has a 2-factor if and only if π - 2 is graphic. This is achieved by obtaining a structure theorem regarding s.c. graphs without a 2-factor. Another interesting corollary of the structure theorem is that if G is a s.c. graph of order p?8 with minimum degree at least $\text{p}\text{4}$, then G has a 2-factor and the result is the best possible.     

On the 1-factors of n-connected graphs

L. W. Beineke and M. D. Plummer have recently proved [1] that every n-connected graph with a 1-factor has at least n different 1-factors. The main purpose of this paper is to prove that every n-connected graph with a 1-factor has at least as many as n(n − 2)(n − 4) … 4 · 2, (or: n(n − 2)(n − 4) … 5 · 3) 1-factors. The main lemma used is: if a 2-connected graph G has a 1-factor, then G contains a vertex V (and even two such vertices), such that each edge of G, incident to V, belongs to some 1-factor of G.     

On factorable degree sequences

We call a degree sequence graphic (respectively, k-factorable, connected k-factorable) if there exists a graph (respectively, a graph with a k-factor, a graph with a connected k-factor) with the given degree sequence. In this paper we give a necessary and sufficient condition for a k-factorable sequence to be connected k-factorable when k ? 2. We also prove that every k-factorable sequence is (k − 2) factorable and 2-factorable, and also 1-factorable, when the sequence is of even length. Some conjectures are stated and it is also proved that, if {d_i} and {d_i − k} are graphic, then {d_i − r} is graphic for 0 ≤ r ≤ k provided rn is even.     

On 1-factors of point determining graphs

A graph G is said to be point determining if and only if distinct points of G have distinct neighborhoods. For such a graph G, the nucleus is defined to be the set G″ consisting of all points ν of G for which G-ν is a point determining graph.In [4], Summer exhibited several families of graphs H such that if G⁰ = H, for some point determining graph G, then G has a 1-factor. In this paper, we extend this class of graphs.     

Nowhere-Zero 5-Flows and Even (1,2)-Factors

A graph G = (V, E) admits a nowhere-zero k-flow if there exists an orientation H = (V, A) of G and an integer flow ${\varphi:A \to \mathbb{Z}}$ such that for all ${a \in A, 0 < |\varphi(a)| < k}$ . Tutte conjectured that every bridgeless graphs admits a nowhere-zero 5-flow. A (1,2)-factor of G is a set ${F \subseteq E}$ such that the degree of any vertex v in the subgraph induced by F is 1 or 2. Let us call an edge of G, F-balanced if either it belongs to F or both its ends have the same degree in F. Call a cycle of G F-even if it has an even number of F-balanced edges. A (1,2)-factor F of G is even if each cycle of G is F-even. The main result of the paper is that a cubic graph G admits a nowhere-zero 5-flow if and only if G has an even (1,2)-factor.     

Decompositions of pseudographs into closed trails of even sizes

We consider a graph L_n, with n even, which is a complete graph with an additional loop at each vertex and minus a 1-factor and we prove that it is edge-disjointly decomposable into closed trails of even lengths greater than four, whenever these lengths sum up to the size of the graph L_n. We also show that this statement remains true if we remove from L_n two loops attached to nonadjacent vertices. Consequently, we improve P. Wittmann’s result on the upper bound of the irregular coloring number c(G) of a 2-regular graph G of size n, by determining that this number is, with a discrepancy of at most one, equal to if all components of G have even orders.     

Connected even factors in claw-free graphs

A connected even [2,2s]-factor of a graph G is a connected factor with all vertices of degree i (i=2,4,…,2s), where s?1 is an integer. In this paper, we show that every supereulerian K_1,s-free graph (s?2) contains a connected even [2,2s-2]-factor, hereby generalizing the result that every 4-connected claw-free graph has a connected [2,4]-factor by Broersma, Kriesell and Ryjacek.     

Two-factors in orientated graphs with forbidden transitions

The instance of the problem of finding 2-factors in an orientated graph with forbidden transitions consists of an orientated graph G and for each vertex v of G, a graph H_v of allowed transitions at v. Vertices of the graph H_v are the edges incident to v. An orientated 2-factor F of G is called legal if all the transitions are allowed, i.e. for every vertex v, the two edges of F adjacent to it form an edge in H_v. Deciding whether a legal 2-factor exists in G is NP-complete in general. We investigate the case when the graphs of allowed transitions are taken from some fixed class C. We provide an exact characterization of classes C so that the problem is NP-complete. In particular, we prove a dichotomy for this problem, i.e. that for any class C it is either polynomial or NP-complete.     

Tutte’s 5-flow conjecture for highly cyclically connected cubic graphs

In 1954, Tutte conjectured that every bridgeless graph has a nowhere-zero 5-flow. Let ω(G) be the minimum number of odd cycles in a 2-factor of a bridgeless cubic graph G. Tutte’s conjecture is equivalent to its restriction to cubic graphs with ω≥2. We show that if a cubic graph G has no edge cut with fewer than edges that separates two odd cycles of a minimum 2-factor of G, then G has a nowhere-zero 5-flow. This implies that if a cubic graph G is cyclically n-edge connected and , then G has a nowhere-zero 5-flow.     

Regular pseudo-median graphs

A graph is pseudo-median if for every triple u, v, w of vertices there exists either a unique vertex between each pair of them (if their mutual distances sum up to an even number) or a unique triangle whose edges lie between the three pairs of u, v, w, respectively (if the distance sum is odd). We show that a finite pseudo-median graph is regular if and only if it is the Cartesian product of a hypercube with either a complete graph or a hyper-octahedron. Every self-map of a pseudo-median graph that preserves or collapses edges has an invariant regular pseudo-median subgraph. Furthermore, the set of all vertices minimizing the total distance to the vertices of a pseudo-median graph induces a regular pseudo-median subgraph.     

Minimal non-1-planar graphs

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by no more than one other edge. A non-1-planar graph G is minimal if the graph G-e is 1-planar for every edge e of G. We prove that there are infinitely many minimal non-1-planar graphs (MN-graphs). It is known that every 6-vertex graph is 1-planar. We show that the graph K₇-K₃ is the unique 7-vertex MN-graph.