共查询到20条相似文献,搜索用时 15 毫秒
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. 相似文献
3.
A signed circuit is a minimal signed graph (with respect to inclusion) that admits a nowhere-zero flow. We show that each flow-admissible signed graph on edges can be covered by signed circuits of total length at most , improving a recent result of Cheng et al. To obtain this improvement, we prove several results on signed circuit covers of trees of Eulerian graphs, which are connected signed graphs such that removing all bridges results in a collection of Eulerian graphs. 相似文献
4.
M. Hofmeister 《Journal of Graph Theory》1988,12(3):437-444
Any group of automorphisms of a graph G induces a notion of isomorphism between double covers of G. The corresponding isomorphism classes will be counted. 相似文献
5.
Dong Ye Cun-Quan Zhang 《European Journal of Combinatorics》2012,33(4):624-631
Let H be a cubic graph admitting a 3-edge-coloring c:E(H)→Z3 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]. 相似文献
6.
《Discrete Mathematics》2006,306(8-9):762-778
In this paper we continue our investigations from [R. Häggkvist, K. Markström, Cycle double covers and spanning minors, Technical Report 07, Department of Mathematics, Umeå University, Sweden, 2001, J. Combin. Theory, Ser. B, to appear] regarding spanning subgraphs which imply the existence of cycle double covers. We prove that if a cubic graph G has a spanning subgraph isomorphic to a subdivision of a bridgeless cubic graph on at most 10 vertices then G has a CDC. A notable result is thus that a cubic graph with a spanning Petersen minor has a CDC, a result also obtained by Goddyn [L. Goddyn, Cycle covers of graphs, Ph.D. Thesis, University of Waterloo, 1988]. 相似文献
7.
Ademir Hujdurović 《Discrete Mathematics》2019,342(9):2542-2548
A canonical double cover of a graph is the direct product of and the complete graph on two vertices. In order to answer the question when a canonical double cover of a given graph is a Cayley graph, in 1992 Maru?i? et al. introduced the concept of generalized Cayley graphs. In this paper this concept is generalized to a wider class of graphs, the so-called extended generalized Cayley graphs. It is proved that the canonical double cover of a connected non-bipartite graph is a Cayley graph if and only if is an extended generalized Cayley graph. This corrects an incorrectly stated claim in [Discrete Math. 102 (1992), 279–285]. 相似文献
8.
9.
Let X and G be graphs, such that G is isomorphic to a subgraph of X.An orthogonal double cover (ODC) of X by G is a collection of subgraphs of X, all isomorphic with G, such that (i) every edge of X occurs in exactly two members of and (ii) and share an edge if and only if x and y are adjacent in X. The main question is: given the pair (X,G), is there an ODC of X by G? An obvious necessary condition is that X is regular.A technique to construct ODCs for Cayley graphs is introduced. It is shown that for all (X,G) where X is a 3-regular Cayley graph on an abelian group there is an ODC, a few well known exceptions apart. 相似文献
10.
A collection 𝒫 of n spanning subgraphs of the complete graph Kn is said to be an orthogonal double cover (ODC) if every edge of Kn belongs to exactly two members of 𝒫 and every two elements of 𝒫 share exactly one edge. We consider the case when all graphs in 𝒫 are isomorphic to some tree G and improve former results on the existence of ODCs, especially for trees G of short diameter and for trees of G on few vertices. © 1997 John Wiley & Sons, Inc. J Combin Designs 5:433–441, 1997 相似文献
11.
J. A. Bondy 《Journal of Graph Theory》1990,14(2):259-272
A perfect path double cover (PPDC) of a graph G on n vertices is a family ?? of n paths of G such that each edge of G belongs to exactly two members of ?? and each vertex of G occurs exactly twice as an end of a path of ??. We propose and study the conjecture that every simple graph admits a PPDC. Among other things, we prove that every simple 3-regular graph admits a PPDC consisting of paths of length three. 相似文献
12.
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. 相似文献
13.
《Journal of Combinatorial Theory, Series B》1987,42(3):328-336
An n-tournament Tn is said to be a Kotzig tournament if the n subtournaments of Tn of order n − 1 are isomorphic. And a nonnegative integral vector R is said to be potentially Kotzig if there exists some Kotzig tournament Tn such that its score vector is R. In this paper, a criterion is found for determining whether a non-negative integral vector R is potentially Kotzig. 相似文献
14.
Let Z be a nonsingular plane curve of even degree and U = P 2 — Z. Let : X —> P 2 be tbe double cover ramified over Z and V = —1(U). It is shown that the kernel of the restriction map on Brauer groups" : B(U) —> B(V), is isomorphic to Z/2(2) where ρ— 2 < r <ρ— 1, p being the Picard number of X and if " : Pic P2 —> Pic X is an isomorphism, exactly half of the algebra classes of order 2 in B(X) are restrictions of algebra classes of order 2 in B(U) whose ramification has been split by V. The kernel of the corestriction map 2 B(V) — 2B(U) is shown to be the subgroup consisting of elements fixed by the Galois group. 相似文献
15.
It is shown that for any 4-regular graph G there is a collection F of paths of length 4 such that each edge of G belongs to exactly two of the paths and each vertex of G occurs exactly twice as an endvertex of a path of F. This proves a special case of a conjecture of Bondy. © 1996 John Wiley & Sons, Inc. 相似文献
16.
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. 相似文献
17.
18.
An orthogonal double cover (ODC) of a graph H is a collection G={Gv:v∈V(H)} of |V(H)| subgraphs of H such that every edge of H is contained in exactly two members of G and for any two members Gu and Gv in G, |E(Gu)∩E(Gv)| is 1 if u and v are adjacent in H and it is 0 if u and v are nonadjacent in H. An ODC G of H is cyclic (CODC) if the cyclic group of order |V(H)| is a subgroup of the automorphism group of G. In this paper, we are concerned with CODCs of 4-regular circulant graphs. 相似文献
19.
Karen Seyffarth 《Combinatorica》1993,13(4):477-482
Acycle double cover of a graph,G, is a collection of cycles,C, such that every edge ofG lies in precisely two cycles ofC. TheSmall Cycle Double Cover Conjecture, proposed by J. A. Bondy, asserts that every simple bridgeless graph onn vertices has a cycle double cover with at mostn–1 cycles, and is a strengthening of the well-knownCycle Double Cover Conjecture. In this paper, we prove Bondy's conjecture for 4-connected planar graphs. 相似文献
20.
《组合设计杂志》2002,10(5):283-293
An Orthogonal Double Cover (ODC) of the complete graph Kn by an almost‐hamiltonian cycle is a decomposition of 2Kn into cycles of length n?1 such that the intersection of any two of them is exactly one edge. We introduce a new class of such decompositions. If n is a prime, the special structure of such a decomposition allows to expand it to an ODC of Kn+1 by an almost‐hamiltonian cycle. This yields the existence of an ODC of Kp+1 by an almost‐hamiltonian cycle for primes p of order 3 mod 4 and its eventual existence for arbitrary primes p. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 283–293, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10011 相似文献