On orthogonal double covers of kn and a conjecture of chung and west
โ Scribed by H.-D. O. F. Gronau; R. C. Mullin; P. J. Schellenberg
- Publisher
- John Wiley and Sons
- Year
- 1995
- Tongue
- English
- Weight
- 909 KB
- Volume
- 3
- Category
- Article
- ISSN
- 1063-8539
No coin nor oath required. For personal study only.
โฆ Synopsis
A collection = {GI, CZ, . . . , C,} of spanning subgraphs of K, is called an orthogonal double cover if (i) every edge of K , belongs to exactly two of the Ci's and (ii) any two distinct Ci's intersect in exactly one edge. Chung and West conjectured that there exists an orthogonal double cover of K,, for all n, in which each Ci has maximum degree 2, and proved this result for n in six of the residue classes modulo 12. In another context, Ganter and Gronau showed that for n = 1 mod 3, n # 10, there exists an orthogonal double cover of K,, in which each Ci consists of an isolated vertex and the vertex disjoint union of K3's (actually these orthogonal double covers result from the solution of the directed version of the problem, which reduces to the undirected case when the orientation of the arcs is ignored). Clearly the covers of Ganter and Gronau satisfy the Chung-West requirement. In this article, the configurations of Ganter and Gronau are generalized to include the cases n = 0,2 mod 3, and the results are used to provide a unified solution of the Chung-West problem. For n # 5 mod 6, all the spanning subgraphs in the collection are isomorphic to each other; however, this is not the case when n = 5 mod 6. In addition to solving the Chung-West problem, we also go on to show that for n = 2 mod 3 and n > 287, there exists an orthogonal double cover of K, in which each spanning subgraph Ci consists of the vertex-disjoint union of an isolated vertex, and quadrilateral, and ( n -5 ) / 3 triangles. Of the 96 cases with 2 5 n 5 287, 65 cases are resolved and 31 remain open.
๐ SIMILAR VOLUMES
## Seyffarth, K., Hajos' conjecture and small cycle double covers of planar graphs, Discrete Mathematics 101 (1992) 291-306. We prove that every simple even planar graph on n vertices has a partition of its edge set into at most [(n -1)/2] cycles. A previous proof of this result was given by Tao,
Zs. Tuza conjectured that if a simple graph G does not contain more than k pairwise edge disjoint triangles, then there exists a set of at most 2k edges which meets all triangles in G. We prove this conjecture for K,, 3 -free graphs (graphs that do not contain a homeomorph of K,. 3). Two fractional
An equivalent statement of the circuit double cover conjecture is that every bridgeless graph \(G\) has a circuit cover such that each vertex \(v\) of \(G\) is contained in at most \(d(v)\) circuits of the cover, where \(d(v)\) is the degree of \(v\). Pyber conjectured that every bridgeless graph \(
We discuss the maximum size of uniform intersecting families with covering number at least {. Among others, we construct a large k-uniform intersecting family with covering number k, which provides a counterexample to a conjecture of Lova sz. The construction for odd k can be visualized on an annulu
## Abstract 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 th