Decomposing complete graphs into \(K_{r} \times K_{c}\)'s. (Q1417807)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Decomposing complete graphs into \(K_{r} \times K_{c}\)'s. |
scientific article |
Statements
Decomposing complete graphs into \(K_{r} \times K_{c}\)'s. (English)
0 references
6 January 2004
0 references
Consider a complete graph \(K_n\) of \(n\) vertices, or a complete multipartite graph \(K_{s(t)}\) of \(st\) vertices partitioned into \(s\) subsets of \(t\) vertices, where \((i,j)\) is an edge if \(i\) and \(j\) are not in the same subset. The authors consider the problem of decomposing such graphs into grid-blocks of \(r\) rows and \(c\) columns where each grid point is a vertex and two vertices are collinear if they are in the same row or column of the grid-blocks. These methods use various combinatorial designs.
0 references
Steiner system
0 references
group divisible design
0 references
grid-block
0 references