\(G\)-designs and related designs
type: Item
instance of: scholarly article
title: \(G\)-designs and related designs
zbMATH Open document ID: 0783.05034
DOI: 10.1016/0012-365X(93)90408-L
author: Kazuhiko Ushio
published in: Discrete Mathematics
publication date: 1994-03-10T00:00:00Z
review text: Let \(G\) be a graph with \(k\) vertices and \(\lambda K_ v\) the complete multigraph with \(v\) vertices in which any two distinct vertices are joined by exactly \(\lambda\) edges. A \((v,k,\lambda)\) \(G\)-design is an edge-disjoint decomposition of \(\lambda K_ v\) into \(b\) subgraphs isomorphic to \(G\). A \(G\)-design is balanced if each vertex belongs to exactly \(r\) subgraphs, and is resolvable if \(\lambda K_ v\) can be factorized into \(r\) \(G\)-factors (i.e., spanning subgraphs whose all components are isomorphic to \(G)\). An \((m,n,k,\lambda)\) multipartite \(G\)- design is an edge-disjoint decomposition of a complete multipartite graph with \(m\) parts of \(n\) vertices each, \(\lambda K^ n_ m\), into \(b\) subgraphs isomorphic to \(G\). Balanced and resolvable \((m,n,k,\lambda)\) \(G\)-designs are defined similarly. Necessary conditions for the existence of \(G\)-designs, bipartite \(G\)- designs, multipartite \(G\)-designs, and also of the corresponding balanced and resolvable designs are proved. Furthermore, a survey of the results concerning the existence of \(G\)-designs, bipartite and multipartite \(G\)- designs, balanced \(G\)-designs and resolvable \(G\)-designs is presented for \(G=K_ k\), \(C_ k\) (a cycle with \(k\) vertices), \(P_ k\) (a path with \(k\) vertices), and \(S_ k\) (a star with \(k\) vertices). Some unsolved problems and conjectures are also posed.
Mathematics Subject Classification ID: 05B30
Mathematics Subject Classification ID: 05B05
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 219089
zbMATH Keywords: \(G\)-design
zbMATH Keywords: balanced
zbMATH Keywords: multipartite graph
zbMATH Keywords: resolvable
zbMATH Keywords: problems
zbMATH Keywords: conjectures
reviewed by: Alexander Rosa
MaRDI profile type: Publication
cites work: Factors and factorizations of graphs—a survey
cites work: Q4097307
cites work: Q3872478
cites work: Cycles in digraphs– a survey
cites work: Existence of resolvable path designs
cites work: Decomposition of complete graphs into stars
cites work: Q4053699
cites work: Edge partitions of complete multipartite graphs into equal length circuits
cites work: \(C_ k\)-factorization of complete bipartite graphs
cites work: Balanced incomplete block designs and related designs
cites work: Graph decompositions, handcuffed prisoners and balanced p-designs
cites work: Hamiltonian decompositions of complete graphs
cites work: Resolvable path designs
cites work: Q3720643
cites work: Q5181705
cites work: On the existence of balanced bipartite designs. II
cites work: Resolvable balanced bipartite designs
cites work: Handcuffed designs
cites work: Q5345646
cites work: On the construction of handcuffed designs
cites work: On decomposition of r-partite graphs into edge-disjoint Hamilton circuits
cites work: Q3965439
cites work: Q5525915
cites work: On the cyclic decompositions of the complete graph into polygons with odd number of edges
cites work: Another class of balanced graph designs: Balanced circuit designs
cites work: Decomposition of K//(m,n)(K*//(m,n)) into cycles (circuits) of length 2k
cites work: Decomposition of complete multigraphs into stars
cites work: Decomposition of a complete multigraph into simple paths: nonbalanced handcuffed designs
cites work: Partite-claw-decomposition of a complete multi-partite graph
cites work: Claw-decomposition and evenly-partite-claw-decomposition of complete multi-partite graphs
cites work: On the decomposition ofkn into complete bipartite graphs
cites work: Note on the decomposition of \(\lambda K_{m,n}\) (\(\lambda K^*_{m,n}\)) into paths
cites work: On claw-decomposition of a complete multi-partite graph
cites work: Bipartite decomposition of complete multipartite graphs
cites work: On balanced claw designs of complete multi-partite graphs
cites work: \(P_ 3\)-factorization of complete bipartite graphs
cites work: Q4083463
cites work: On claw-decomposition of complete graphs and complete bigraphs
cites work: Design of a new balanced file organization scheme with the least redundancy
description: scientific article; zbMATH DE number 219089