共查询到20条相似文献,搜索用时 0 毫秒
1.
Dezheng Xie 《Discrete Mathematics》2009,309(14):4682-4689
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,f1) and (D,f2) is an (h,k)-flow parity-pair-cover of G if the union of their supports covers the entire graph; f1 is an h-flow and f2 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,f1) and (D,f2) is an (h,k)-flow even-disjoint-pair-cover of G if the union of their supports covers the entire graph, f1 is an h-flow and f2 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. 相似文献
2.
A cycle permutation graph is obtained by taking two n-cycles each labeled 1, 2,…, n, along with the edges obtained by joining i in the first copy to α(i) in the second, where α ∈ Sn. A characterization of the intersection between cycle permutation graphs and the generalized Petersen graphs as defined by Watkins (J. Combin. Theory6 (1969), 152–164), is given. 相似文献
3.
Ju-Mok Oh 《Discrete Mathematics》2009,309(23-24):6590-6611
4.
5.
Let be a finite -regular graph with a proper edge coloring. An edge Kempe switch is a new proper edge coloring of obtained by switching the two colors along some bichromatic cycle. We prove that any other edge coloring can be obtained by performing finitely many edge Kempe switches, provided that is replaced with a suitable finite covering graph. The required covering degree is bounded above by a constant depending only on . 相似文献
6.
Afsaneh Mehran 《manuscripta mathematica》2007,123(2):205-235
Besides its construction as a quotient of an abelian surface, a Kummer surface can be obtained as the quotient of a K3 surface
by a -action. In this paper, we classify all such K3 surfaces. Our classification is expressed in terms of period lattices and
extends Morrison’s criterion of K3 surfaces with a Shioda–Inose structure. Moreover, we list all the K3 surfaces associated
to a general Kummer surface and provide very geometrical examples of this phenomenon. 相似文献
7.
A solvable cover of a graph is a regular cover whose covering transformation group is solvable. In this paper, we show that a solvable cover of a graph can be decomposed into layers of abelian covers, and also, a lift of a given automorphism of the base graph of a solvable cover can be decomposed into layers of lifts of the automorphism in the layers of the abelian covers. This procedure is applied to classify metacyclic covers of the tetrahedron branched at face-centers. 相似文献
8.
Bodo Manthey 《Discrete Applied Mathematics》2009,157(7):1470-1480
A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. An L-cycle cover is a cycle cover in which the length of every cycle is in the set L⊆N.We investigate how well L-cycle covers of minimum weight can be approximated. For undirected graphs, we devise non-constructive polynomial-time approximation algorithms that achieve constant approximation ratios for all sets L. On the other hand, we prove that the problem cannot be approximated with a factor of 2−ε for certain sets L.For directed graphs, we devise non-constructive polynomial-time approximation algorithms that achieve approximation ratios of O(n), where n is the number of vertices. This is asymptotically optimal: We show that the problem cannot be approximated with a factor of o(n) for certain sets L.To contrast the results for cycle covers of minimum weight, we show that the problem of computing L-cycle covers of maximum weight can, at least in principle, be approximated arbitrarily well. 相似文献
9.
10.
Genghua Fan 《Journal of Graph Theory》1997,25(3):229-242
Some new results on minimum cycle covers are proved. As a consequence, it is obtained that the edges of a bridgeless graph G can be covered by cycles of total length at most , and at most if G contains no circuit of length 8 or 12. © 1997 John Wiley & Sons, Inc. J Graph Theory 25:229–242, 1997 相似文献
11.
An acyclic graphoidal cover of a graph G is a collection ψ of paths in G such that every path in ψ has at least two vertices, every vertex of G is an internal vertex of at most one path in ψ and every edge of G is in exactly one path in ψ. The minimum cardinality of an acyclic graphoidal cover of G is called the acyclic graphoidal covering number of G and is denoted by ηa. A path partition of a graph G is a collection P of paths in G such that every edge of G is in exactly one path in P. The minimum cardinality of a path partition of G is called thepath partition number of G and is denoted by π. In this paper we determine ηa and π for several classes of graphs and obtain a characterization of all graphs with Δ 4 and ηa = Δ − 1. We also obtain a characterization of all graphs for which ηa = π. 相似文献
12.
An acyclic graphoidal cover of a graph G is a collection ψ of paths in G such that every path in ψ has at least two vertices, every vertex of G is an internal vertex of at most one path in ψ and every edge of G is in exactly one path in ψ. The minimum cardinality of an acyclic graphoidal cover of G is called the acyclic graphoidal covering number of G and is denoted by ηa. A path partition of a graph G is a collection P of paths in G such that every edge of G is in exactly one path in P. The minimum cardinality of a path partition of G is called the path partition number of G and is denoted by π. In this paper we determine ηa and π for several classes of graphs and obtain a characterization of all graphs with Δ 4 and ηa = Δ − 1. We also obtain a characterization of all graphs for which ηa = π. 相似文献
13.
A near-polygonal graph is a graph Γ which has a set C of m-cycles for some positive integer m such that each 2-path of Γ is contained in exactly one cycle in C. If m is the girth of Γ then the graph is called polygonal. We introduce a method for constructing near-polygonal graphs with 2-arc transitive automorphism groups. As special cases, we obtain several new infinite families of polygonal graphs. 相似文献
14.
15.
Genghua Fan 《Journal of Graph Theory》1994,18(2):131-141
Let G be a bridgeless cubic graph. We prove that the edges of G can be covered by circuits whose total length is at most (44/27) |E(G)|, and if Tutte's 3-flow Conjecture is true, at most (92/57) |E(G)|. 相似文献
16.
Rui Xu 《Discrete Mathematics》2009,309(5):1041-1042
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. 相似文献
17.
18.
19.
20.
We construct a new symmetric Hamilton cycle decomposition of the complete graph Kn for odd n > 7. © 2003 Wiley Periodicals, Inc. 相似文献