✦ LIBER ✦

Decompositions of Edge-Colored Complete Graphs

✍ Scribed by Esther R. Lamken; Richard M. Wilson

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 538 KB
Volume: 89
Category: Article
ISSN: 0097-3165
DOI: 10.1006/jcta.1999.3005

No coin nor oath required. For personal study only.

✦ Synopsis

We prove an asymptotic existence theorem for decompositions of edge-colored complete graphs into prespecified edge-colored subgraphs. Many combinatorial design problems fall within this framework. Applications of our main theorem require calculations involving the numbers of edges of each color and degrees of each color class of edges for the graphs allowed in the decomposition. We do these calculations to provide new proofs of the asymptotic existence of resolvable designs, near resolvable designs, group divisible designs, and grid designs. Two further applications are the asymptotic existence of skew Room d-cubes and the asymptotic existence of (v, k, 1)-BIBDs with any group of order k&1 as an automorphism group.

📜 SIMILAR VOLUMES

Almost regular edge colorings and regula

Almost regular edge colorings and regular decompositions of complete graphs

✍ Darryn Bryant; Barbara Maenhaut 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB

## Abstract For __k__ = 1 and __k__ = 2, we prove that the obvious necessary numerical conditions for packing __t__ pairwise edge‐disjoint __k__‐regular subgraphs of specified orders __m__~1~,__m__~2~,… ,__m__~t~ in the complete graph of order __n__ are also sufficient. To do so, we present an edge

Properly colored hamilton cycles in edge

Properly colored hamilton cycles in edge-colored complete graphs

✍ N. Alon; G. Gutin 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 156 KB 👁 3 views

It is shown that, for ⑀ ) 0 and n ) n ⑀ , any complete graph K on n vertices 0 ' Ž . whose edges are colored so that no vertex is incident with more than 1 y 1r 2 y ⑀ n edges of the same color contains a Hamilton cycle in which adjacent edges have distinct colors. Moreover, for every k between 3 and

Edge-colored complete graphs with altern

Edge-colored complete graphs with alternating cycles

✍ S.H. Whitesides 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 648 KB

We prove that if the edges of the complete graph on n ~4 vertices are colored so that no vertex is on more than A edges of the same color, 1 c A < n -2,, then the graph has cycles of all lengths 3 through n with no A consecutive edges the same color.

Characterization of edge-colored complet

Characterization of edge-colored complete graphs with properly colored Hamilton paths

✍ Jinfeng Feng; Hans-Erik Giesen; Yubao Guo; Gregory Gutin; Tommy Jensen; Arash Ra 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 164 KB

## Abstract An edge‐colored graph __H__ is properly colored if no two adjacent edges of __H__ have the same color. In 1997, J. Bang‐Jensen and G. Gutin conjectured that an edge‐colored complete graph __G__ has a properly colored Hamilton path if and only if __G__ has a spanning subgraph consisting

Designs with mutually orthogonal resolut

Designs with mutually orthogonal resolutions and decompositions of edge-colored graphs

✍ E. R. Lamken 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 298 KB

## Abstract Two resolutions __R__ and __R__^′^ of a combinatorial design are called orthogonal if |__R__~__i__~∩__R__|≤1 for all __R__~__i__~∈__R__ and __R__∈__R__^′^. A set __Q__={__R__^1^, __R__^2^, …, __R__^__d__^} of __d__ resolutions of a combinatorial design is called a set of mutually orthog

Coloring the Edges of a Complete Graph

✍ Annamaria G. Varga 📂 Article 📅 1972 🏛 John Wiley and Sons 🌐 English ⚖ 577 KB