Orthogonal decomposition and packing of complete graphs
type: Item
instance of: scholarly article
title: Orthogonal decomposition and packing of complete graphs
zbMATH Open document ID: 0938.05052
author: Yair Caro
author: Raphael Yuster
published in: Journal of Combinatorial Theory. Series A
publication date: 1999-12-20T00:00:00Z
review text: A \(k\)-orthogonal \(H\)-decomposition of a graph \(G\) is a set of \(k\) edge-decompositions of \(G\) into copies of \(H\) such that any two copies of \(H\) from different decompositions in the set intersect on at most one edge. The authors prove that there is \(N= N(k,r)\) such that for every \(n>N\), if \(K_n\) has a \(K_r\)-decomposition then it also has a \(k\)-orthogonal \(K_r\)-decomposition. The authors also present a method to find a \(k\)-orthogonal packing of \(K_n\) if \(K_n\) does not have a \(K_r\)-decomposition. They consider the complexity of deciding the existence of \(k\)-orthogonal decompositions and propose the following conjecture: for every fixed graph \(H\) having at least three edges in some connected component, and for every fixed positive integer \(k\), it is NP-complete to decide whether a given input graph has a \(k\)-orthogonal \(H\)-decomposition.
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 1356435
zbMATH Keywords: edge-decompositions
zbMATH Keywords: packing
reviewed by: Mirosław Truszczyński
MaRDI profile type: Publication
full work available at URL: jcta.1999.2981
OpenAlex ID: W2042976533
cites work: On the existence of super-simple designs with block size 4
cites work: Q4222171
cites work: Q4026144
cites work: Orthogonal matchings
cites work: Q3760557
cites work: Q4729795
cites work: The intersection problem for \(K_4-e\) designs
cites work: The intersection problem for star designs
cites work: Q4858160
cites work: Super-simple designs with \(v\leq 32\)
cites work: Q3852212
cites work: On orthogonal double covers of graphs
cites work: Q4033006
cites work: Packing graphs: The packing problem solved
cites work: Covering graphs: The covering problem solved
cites work: Q4873725
cites work: Q4014297
cites work: Q4305537
cites work: Construction of Steiner quadruple systems having a prescribed number of blocks in common
cites work: On a problem of Hering concerning orthogonal covers of \({\mathbf K}_ n\)
cites work: Q4016822
cites work: Orthogonal double covers of complete graphs by trees
cites work: On orthogonal double covers of kn and a conjecture of chung and west
cites work: Q5620621
cites work: Intersections of Steiner quadruple systems
cites work: Q4697578
cites work: Q4304329
cites work: Intersections among Steiner systems
cites work: Q4017180
cites work: Steiner Triple Systems Having a Prescribed Number of Triples in Common
cites work: Steiner quadruple systems having a prescribed number of quadruples in common
cites work: On large sets of disjoint Steiner triple systems. VI
cites work: Q4894959
cites work: Intersection Properties of Steiner Systems
cites work: Non-trivial \(t\)-designs without repeated blocks exist for all \(t\)
cites work: A completion of Lu's determination of the spectrum for large sets of disjoint Steiner triple systems
cites work: Q4026154
cites work: Q4002255
cites work: Q4083463
DOI: 10.1006/JCTA.1999.2981
Recommended article: Orthogonal decompositions of complete digraphs
Recommended article: Packings in complete graphs
Recommended article: Combinatorial and computational aspects of graph packing and graph decomposition
Recommended article: Packing graphs in their complements
Recommended article: Q3222883
Recommended article: Edge decompositions and rooted packings of graphs
Recommended article: Packings by Complete Bipartite Graphs
Recommended article: Q4390611
Recommended article: Packing \(d\)-degenerate graphs
Recommended article: Orthogonal factorizations of graphs
description: scientific article; zbMATH DE number 1356435