✦ LIBER ✦

Orthogonal Decomposition and Packing of Complete Graphs

✍ Scribed by Yair Caro; Raphael Yuster

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 165 KB
Volume: 88
Category: Article
ISSN: 0097-3165
DOI: 10.1006/jcta.1999.2981

No coin nor oath required. For personal study only.

✦ Synopsis

An H-decomposition of a graph G is a partition of the edge-set of G into subsets, where each subset induces a copy of the graph H. A k-orthogonal H-decomposition of a graph G is a set of k H-decompositions of G, such that any two copies of H in distinct H-decompositions intersect in at most one edge. In case G=K n and H=K r , a k-orthogonal K r -decomposition of K n is called an (n, r, k) completely reducible super-simple design. We prove that for any two fixed integers r and k, there exists N=N(k, r) such that for every n>N, if K n has a K r -decomposition, then K n also has an (n, r, k) completely-reducible super-simple design. If K n does not have a K r -decomposition, we show how to obtain a k-orthogonal optimal K r -packing of K n . Complexity issues of k-orthogonal H-decompositions are also treated.

📜 SIMILAR VOLUMES

Packing and Decomposition of Graphs with

Packing and Decomposition of Graphs with Trees

✍ Raphael Yuster 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 214 KB

Let H be a tree on h 2 vertices. It is shown that if n is sufficiently large and G=(V, E ) is an n-vertex graph with $(G) wnÂ2x , then there are w |E |Â(h&1)x edge-disjoint subgraphs of G which are isomorphic to H. In particular, if h&1 divides |E | then there is an H-decomposition of G. This result

Commuting decompositions of complete gra

Commuting decompositions of complete graphs

✍ Saieed Akbari; Allen Herman 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 129 KB

## Abstract We say that two graphs __G__ and __H__ with the same vertex set commute if their adjacency matrices commute. In this article, we show that for any natural number __r__, the complete multigraph __K__ is decomposable into commuting perfect matchings if and only if __n__ is a 2‐power. Also

Packing complete multipartite graphs wit

Packing complete multipartite graphs with 4-cycles

✍ Elizabeth J. Billington; Hung-Lin Fu; C.A. Rodger 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 394 KB 👁 1 views

Decomposition of complete graphs into 5-

Decomposition of complete graphs into 5-cubes

✍ D. Bryant; S. I. El-Zanati; B. Maenhaut; C. Vanden Eynden 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 116 KB

## Abstract Necessary conditions for the complete graph on __n__ vertices to have a decomposition into 5‐cubes are that 5 divides __n__ − 1 and 80 divides __n__(__n__ − 1)/2. These are known to be sufficient when __n__ is odd. We prove them also sufficient for __n__ even, thus completing the spectr

Closed trail decompositions of complete

Closed trail decompositions of complete equipartite graphs

✍ Andrea Burgess; Mateja Šajna 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 314 KB

## Abstract The complete equipartite graph \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}$K\_m \* {\overline{K\_n}}$\end{document} has mn vertices partitioned into __m__ parts of size __n__, with two vertices adjacent if and only if they are in different parts. In this paper,

On resolvable tree-decompositions of com

On resolvable tree-decompositions of complete graphs

✍ Zbigniew Lonc 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 355 KB 👁 1 views

A partition of the edge set of a graph H into subsets inducing graphs H,, . . . , H, isomorphic to a graph G is said to be a G-decomposition of H. A G-decomposition of H is resolvable if the set {H,, . . . , H,} can be partitioned into subsets, called resolution classes, such that each vertex of H