๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

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


Hajรณs' conjecture and small cycle double
โœ Karen Seyffarth ๐Ÿ“‚ Article ๐Ÿ“… 1992 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 865 KB

## 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,

On a conjecture of Tuza about packing an
โœ Michael Krivelevich ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 312 KB

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

Circuit Coverings of Graphs and a Conjec
โœ G.H. Fan ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 260 KB

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 \(

Covers in Uniform Intersecting Families
โœ Peter Frankl; Katsuhiro Ota; Norihide Tokushige ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 446 KB

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

Perfect path double covers of graphs
โœ J. A. Bondy ๐Ÿ“‚ Article ๐Ÿ“… 1990 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 513 KB

## 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