On complementary decompositions of the complete graph
type: Item
instance of: scholarly article
title: On complementary decompositions of the complete graph
zbMATH Open document ID: 0674.05050
DOI: 10.1007/BF01788658
author: Andrew Granville
author: Alexandros Moisiadis
author: R. S. Rees
published in: Graphs and Combinatorics
publication date: 1989-01-01T00:00:00Z
review text: In this remarkable paper the authors consider decompositions \(K_ n\to H\), where H is either \(P_ 3\) (the path with 3 edges) or the complete bipartite graph \(K_{1,3}\), with the property that upon taking the complement of each graph in the decomposition one obtains a new decomposition \(K_ n\to H^ c.\) Two main results are obtained. The first is that a complementary decomposition \(K_ n\to P_ 3\) exists if and only if \(n\equiv 1\) modulo 3. The second result is that whenever \(n\equiv 1\) modulo 6 there exists a pair of complementary decompositions \(K_ n\to K_{1,3}\) and \(K_ n\to P_ 3\) (on the same \(K_ n)\) with the property that the graphs \(H_ 1,...,H_ t\) and \(J_ 1,...,J_ t\) corresponding to these decompositions satisfy \(H_ i\cup H^ c_ i=J_ i\cup J^ c_ i\) for \(i=1,...,t\) (that is, each decomposition gives rise to the same two- fold covering of \(K_ n\) by \(K_ 4s).\) More recent work involving subdesigns in such decompositions can be found in \textit{R. Rees} and \textit{D. R. Stinson}, On Combinatorial Designs with Subdesigns, Discrete Math. 77, 259-279 (1989), and in \textit{R. Rees} and \textit{C. A. Rodger}, Subdesigns in Complementary Path Decompositions and Incomplete Two-fold Designs with Block Size Four, to appear in Graphs and Combinatorics.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05B05
zbMATH DE Number: 4103115
zbMATH Keywords: graph decompositions
zbMATH Keywords: balanced incomplete block designs
zbMATH Keywords: BIBD
MaRDI profile type: Publication
cites work: Optimal packings of \(K_4\)'s into a \(K_n\)
cites work: The Existence and Construction of Balanced Incomplete Block Designs
cites work: Steiner pentagon systems
cites work: Q3719664
cites work: The spectrum of nested Steiner triple systems
cites work: A construction for authentication/secrecy codes from certain combinatorial designs
Recommended article: On a decomposition of complete graphs
Recommended article: Decompositions of Complete Graphs
Recommended article: Q4842726
Recommended article: On the completeness of decomposable properties of graphs
Recommended article: On decompositions of complete hypergraphs
Recommended article: Q5115501
Recommended article: Q3006095
Recommended article: Commuting decompositions of complete graphs
Recommended article: On the decomposition of graphs into complete bipartite graphs
Recommended article: Decompositions of complete multipartite graphs
description: scientific article; zbMATH DE number 4103115