On Group-connectivity, Cycle Cover And Some Related Problems

We discuss four problems in this paper.Firstly, let G be a 3-connected simple cubic graph on≥8 vertices. We get a upper bound of a cycle cover of graph G.A cycle cover of a graph G is a collection (?) of cycles of G such that every edge of G lies in at least one member of (?). Barnette [1] proved that if G is a 3-connected simple planar graph on n vertices, then the edges of G can be covered by at most (n+1)/2 cycles. Lai and Li [5] proved that every 2-connected simple cubic graph on n> 6 vertices admits a cycle cover of size at most [n/4]. Strengthening the connectivity, by considering the cyclic-κ-edge cut of G, we proved in this paper that G admits a cycle cover of size at most fn/6] if and only if G is not one of five specified graphs{G1, G2, G3, G4, G5} (see Fig.1).Secondly, the nowhere-zero 3-flow’s problem of a Cayley graph of a dihedral group and of valence at least 4.In this section, let G be a group, X denote a Cayley graph Cay(G, S). A subset S of a group G is called a Cayley set if 1(?) S and x∈S implies x-1∈S, where 1 is the identity element of G. The Cayley graph of G with respect to a Cayley set S, Cay(G, S), is the graph with vertex-set G in which x,y∈G are adjacent if and only if x-l y∈S.The well-known 3-flow conjecture is due to Tutte [18,19], as follows:every bridgeless graph containing no 3-edge-cut admits a nowhere-zero 3-flow. However, it is still open. Jaeger et al. [11,12] further showed many interesting and important results. Potocnik et al. [17] proved that every Cayley graph of an abelian group and of valence at least 4 admits a nowhere-zero 3-flow. Nanasiova and Skoviera [14] proved that a Cayley graph of degree at least 4 on a nilpotent group admits a nowhere-zero 3-flow. However, the dihedral group D2n is nilpotent if and only if n is a power of 2 (see Exercise 8, p.106 in [13]). Thus, we consider nowhere-zero 3-flows in the Cayley graphs of a dihedral group, which is non-abelian. Following the idea, we prove every Cayley graph of a dihedral group and of valence at least 4 admits a nowhere-zero 3-flow.Thirdly, we are concerned whether G is A-connected or not, where G∈C(6,5) and A is an abelian group with |A|≥4。For integers k; and l with k>0 and l≥0, let C(k,l) denote the family of 2-edge connected graphs G such that for each edge cut S(?) E(G) with two or three edges, each component of G- S has at least (|V(G)|-l)/k vertices. In this paper, k=6,l=5. Set A*=A-{0}. A graph G is A-connected if for any function there exists an orientation of G and a function f:E(G)→A* such that (?)f(v)=b(v) for any vertex v∈V(G), where In this paper, we show that if G is 3-edge connected and G∈C(6,5), then G is not A-connected if and only if G can be A-contracted to the Petersen graph.Finally, we consider the Z3-connectivity of graphs which satisfies some degree sum condition.Many people have obtained some results on Z3-connectivity. Ore has got some results in terms of degree sum and given the Ore-condition, that is the degree sum of any two nonadjacent vertices is equal or more than the vertex number of G. Luo [35] proved if G satisfies the Ore-condition, then G is Z3-connected if and only if G is not one of special 12 graphs. The Ore-condition can be thought as the degree sum of any 2-independent set of G is equal or more than the vertex number of G. So we extend this condition to any 3-independent set of G, that is, d(x)+d(y)+d(z)≥3n/2 for any 3-independent set{x,y,z} of G. We proved if whenα(G)≥3, d(x)+d(y)+d(z)≥3n/2 for any 3-independent set{x,y,z} and whenα(G)≤2, d(x)+d(y)≥n for any 2-independent set{x,y} of G, then G is one of the 12 special graphs or G can be Z3-contracted to one of the graphs{K1,K3,K4,K4-,G5}, where G is a 2-edge connected simple graph.