Almost all 5-regular graphs have a 3-flow

Tutte conjectured in 1972 that every 4-edge–connected graph has a nowhere-zero 3-flow. This has long been known to be equivalent to the conjecture that every 5-regular 4-edge–connected graph has an edge orientation in which every in-degree is either 1 or 4. We show that the assertion of the conjecture holds asymptotically almost surely for random 5-regular graphs. It follows that the conjecture holds for almost all 4-edge–connected 5-regular graphs.     

HAMILTONIAN DECOMPOSITION OF CAYLEY GRAPHS OF ORDERS p~2 AND pq

1. IntroductionLet G be a finite group and S a subset of G such that S--1 ~ S, and 1 f S. The Cayleygraph Cay (G, S) is defined as the simple graph with V ~ G, and E = {glgZ I g,'g, or g,'g,6 S, gi, gi E G}. Cay (G, S) is vertex-transitive, and it is connected if and only if (S) = G,i.e. S is a generating set of G[1]. If G = Zn, then Cay (Zn, S) is called a circulant graph. Ithas been proved that any connected Cayley graph on a finite abelian group is hamiltonianl2].Furthermore, …     

Transitive digraphs with more than one end

In this paper we investigate infinite, locally finite, connected, transitive digraphs with more than one end. For undirected graphs with these properties it has been shown that they are trees as soon as they are 2-arc transitive. In the case of digraphs the situation is much more involved. We show that these graphs can have both thick and thin ends, even if they are highly arc transitive. Hence they are far away from being ‘tree-like’. On the other hand all known examples of digraphs with more than one end are either highly arc transitive or at most 1-arc transitive. We conjecture that infinite, locally finite, connected, 2-arc transitive digraphs with more than one end are highly arc transitive and prove that this conjecture holds for digraphs with prime in- and out-degree and connected cuts.     

论连通图的可重构性

本文我们利用带权核子图的可重构性证明了连通图是可重构的,从而证明了重构猜想为真.     

On the Congruences of Some Combinatorial Numbers

In this paper, we apply Lucas' theorem to evaluate the congruences of several combinatorial numbers, including the central Delannoy numbers and a class of Apéry-like numbers, the numbers of noncrossing connected graphs, the numbers of total edges of all noncrossing connected graphs on n vertices, etc. One of these results verifies a conjecture given by Deutsch and Sagan recently. In the end, we use an automaton to explain the idea of our approach.     

A New Method for Enumerating Independent Sets of a Fixed Size in General Graphs

We develop a new method for enumerating independent sets of a fixed size in general graphs, and we use this method to show that a conjecture of Engbers and Galvin [7] holds for all but finitely many graphs. We also use our method to prove special cases of a conjecture of Kahn [13]. In addition, we show that our method is particularly useful for computing the number of independent sets of small sizes in general regular graphs and Moore graphs, and we argue that it can be used in many other cases when dealing with graphs that have numerous structural restrictions.     

Hamiltonian decomposition of Cayley graphs of ordersp 2 andpq

In this paper, it is proved that any connected Cayley graph on an abelian group of order pq orp ² has a hamiltonian decomposition, wherep andq are odd primes. This result answers partially a conjecture of Alspach concerning hamiltonian decomposition of 2k-regular connected Cayley graphs on abelian groups.     

Colourings of oriented connected cubic graphs

In this note we show every orientation of a connected cubic graph admits an oriented 8-colouring. This lowers the best-known upper bound for the chromatic number of the family of orientations of connected cubic graphs. We further show that every such oriented graph admits a 2-dipath 7-colouring. These results imply that either the oriented chromatic number for the family of orientations of connected cubic graphs equals the 2-dipath chromatic number or the long-standing conjecture of Sopena (Sopena, 1997) regarding the chromatic number of orientations of connected cubic graphs is false.     

Cuts in matchings of 3-connected cubic graphs

We discuss conjectures on Hamiltonicity in cubic graphs (Tait, Barnette, Tutte), on the dichromatic number of planar oriented graphs (Neumann-Lara), and on even graphs in digraphs whose contraction is strongly connected (Hochstättler). We show that all of them fit into the same framework related to cuts in matchings. This allows us to find a counterexample to the conjecture of Hochstättler and show that the conjecture of Neumann-Lara holds for all planar graphs on at most 26 vertices. Finally, we state a new conjecture on bipartite cubic oriented graphs, that naturally arises in this setting.     

The reconstruction of separable graphs with 2-connected trunks that are series-parallel networks

A 2-connected graph has a cleavage unit-virtual edge decomposition which is due to Tutte [8]. Cleavage units are either polygons, bonds (planar duals to polygons) or 3-connected simple graphs. When all cleavage units are polygons or bonds, such graphs are called series-parallel networks. The Ulam graph reconstruction conjecture is open for the class of connected graphs containing circuits and/or pendant vertices. Such graphs can be expressed uniquely in terms of a trunk, a connected subgraph without pendant vertices, and a tree-growth, a forest each connected component of which meets the trunk in a unique root vertex. This paper establishes the reconstruction conjecture when the trunk is a series-parallel network and the tree-growth is ‘non-trivial’. This is accomplished by means of Tutte's decomposition of the trunk, and group theoretical techniques first developed in [2]. Use is made of the restricted nature of the automorphism groups of the polygon and bond cleavage units of the trunk.     

Nowhere‐Zero 5‐Flows On Cubic Graphs with Oddness 4

Tutte's 5‐flow conjecture from 1954 states that every bridgeless graph has a nowhere‐zero 5‐flow. It suffices to prove the conjecture for cyclically 6‐edge‐connected cubic graphs. We prove that every cyclically 6‐edge‐connected cubic graph with oddness at most 4 has a nowhere‐zero 5‐flow. This implies that every minimum counterexample to the 5‐flow conjecture has oddness at least 6.     

The graph formulation of the union-closed sets conjecture

The union-closed sets conjecture asserts that in a finite non-trivial union-closed family of sets there has to be an element that belongs to at least half the sets. We show that this is equivalent to the conjecture that in a finite non-trivial graph there are two adjacent vertices each belonging to at most half of the maximal stable sets. In this graph formulation other special cases become natural. The conjecture is trivially true for non-bipartite graphs and we show that it holds also for the classes of chordal bipartite graphs, subcubic bipartite graphs, bipartite series-parallel graphs and bipartitioned circular interval graphs. We derive that the union-closed sets conjecture holds for all union-closed families being the union-closure of sets of size at most three.     

Simply sequentially additive labelings of 2-regular graphs

We conjecture that any 2-regular simple graph has an SSA labeling. We provide several special cases to support our conjecture. Most of our constructions are based on Skolem sequences and on an extension of it. We establish a connection between simply sequentially additive labelings of 2-regular graphs and ordered graceful labelings of spiders.     

Almost all Cayley graphs are hamiltonian

It has been conjectured that there is a hamiltonian cycle in every finite connected Cayley graph. In spite of the difficulty in proving this conjecture, we show that almost all Cayley graphs are hamiltonian. That is, as the order n of a groupG approaches infinity, the ratio of the number of hamiltonian Cayley graphs ofG to the total number of Cayley graphs ofG approaches 1.Supported by the National Natural Science Foundation of China, Xinjiang Educational Committee and Xinjiang University.     

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     

Note on cycle double covers of graphs

Kriesell [M. Kriesell, Contractions, cycle double covers and cyclic colorings in locally connected graphs, J. Combin. Theory Ser. B 96 (2006) 881-900] proved the cycle double cover conjecture for locally connected graphs. In this note, we give much shorter proofs for two stronger results.     

Decomposition of cubic graphs with a 2-factor consisting of three cycles

The 3-Decomposition Conjecture states that every connected cubic graph can be decomposed into a spanning tree, a 2-regular subgraph and a matching. We prove that this conjecture is true for connected cubic graphs with a 2-factor consisting of three cycles.     

Simpler counterexamples to the edge-reconstruction conjecture for infinite graphs

A nonisomorphic, edge-hypomorphic pair of countable forests is constructed, hereby providing a counterexample to the edge-reconstruction conjecture for infinite graphs that is simpler than the counterexamples previously given by C. Thomassen. In addition, to answer the questions posed by C. Thomassen in a previous paper, it is shown that there is a countable forest that is vertex-reconstructible but not edge-reconstructible, and that there is a countable, connected graph with these properties.     

Remarks on the bondage number of planar graphs

The bondage number b(G) of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph with domination number greater than the domination number γ(G) of G. In 1998, J.E. Dunbar, T.W. Haynes, U. Teschner, and L. Volkmann posed the conjecture b(G)Δ(G)+1 for every nontrivial connected planar graph G. Two years later, L. Kang and J. Yuan proved b(G)8 for every connected planar graph G, and therefore, they confirmed the conjecture for Δ(G)7. In this paper we show that this conjecture is valid for all connected planar graphs of girth g(G)4 and maximum degree Δ(G)5 as well as for all not 3-regular graphs of girth g(G)5. Some further related results and open problems are also presented.     

Every longest circuit of a 3‐connected,K3,3‐minor free graph has a chord

Carsten Thomassen conjectured that every longest circuit in a 3‐connected graph has a chord. We prove the conjecture for graphs having no K_3,3 minor, and consequently for planar graphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 293–298, 2008