Survey on balanced graph and hypergraph designs
Let \(V\) be a \(v\)-set, \(K_v\) be the complete graph on \(V\). Let \(G=(X,\mathcal{E})\) be a graph on \(n\) vertices. A \(G\)-design is a pair \(\Sigma=(V,\mathcal{B})\), where \(\mathcal{B}=\{G_1,\dots, G_b\}\), such that: \N\begin{itemize}\N\item[(1)] \(G_i\cong G\) for any \(i=1,\dots,b\); \N\item[(2)] for any \(x, y\in V\), \(x\neq y\), there exists a \(G_i\) such that \(\{x, y\}\in E(G_i)\) for \(i=1,\dots, b\).\N\end{itemize}\N\NThe elements of \(\mathcal{B}\) are called blocks. The degree of a vertex \(x\in V\) is the number of blocks of \(\mathcal{B}\) containing \(x\). \(\Sigma\) is called balanced if there exists \(d\in N\) such that \(d(x)= d\) for all \(x\in V\). \(\Sigma\) is usually called a \(G\)-decomposition of \(K_v\).\N\NLet \(K_v^{(3)}\) be the complete \(3\)-uniform hypergraph on \(V\) and let \( H=(X,\mathcal{E})\) be a 3-uniform hypergraph with \(n =|X|\) and \(m=|E|\). An \(H\)-design is a pair \(\Sigma=(V,\mathcal{B})\), where \(\mathcal{B}=\{H_1,\dots, H_b\}\) satisfies \N\begin{itemize}\N\item[(1)] \(H_i\cong H\) for any \(i=1,\dots,b\) and \N\item[(2)] for any \(x, y, z\in V,\) pairwise different, there exists an \(H_i\) such that such that \(\{x,y,z\} \in E(H_i)\) for \(i=1,\dots, b\).\N\end{itemize}\NThe elements of \(\mathcal{B}\) are called blocks and we say that \(\sum\) is an \(H\)-decomposition \(K_v^{(3)}\). The definition of balanced (strongly balanced) hypergraph design is analogous to the one given in the case of graph designs.\N\NIn this paper, the authors summarize some known results on balanced, strongly balanced, locally balanced, and strictly balanced \(G\)-designs. They consider some general cases such as those of cycles, paths, stars, and complete bipartite graphs, and examine the case of graphs with few vertices. For the hypergraph design case, they summarize some known results on balanced (strongly balanced) 3-hypergraphs.
- \(G\)-decomposition of \(K_n\), where G has four vertices or less
- Balanced \(P^{(3)} (2, 4)\)-designs
- Balanced and strongly balanced 4-kite designs
- Balanced and strongly balanced \(P_k\)-designs
- Balanced House-systems and nestings.
- Cycle decompositions of K_n and K_n-I
- Cycle decompositions. III: Complete graphs and fixed length cycles.
- Degree- and orbit-balanced -designs when has five vertices
- Edge balanced star‐hypergraph designs and vertex colorings of path designs
- Further results concerning the existence of handcuffed designs
- Graph decompositions, handcuffed prisoners and balanced p-designs
- Handcuffed designs
- Handcuffed designs
- scientific article; zbMATH DE number 3710227 (Why is no real title available?)
- scientific article; zbMATH DE number 3428942 (Why is no real title available?)
- scientific article; zbMATH DE number 3308125 (Why is no real title available?)
- On the construction of handcuffed designs
- On the existence of balanced bipartite designs. II
- Some techniques for the construction of hyperpath-designs -- a survey
- The CRC handbook of combinatorial designs
- The spectrum of balanced \(P^{(3)}(1, 5)\)-designs
- Tree-designs with balanced-type conditions
This page was built for publication: Survey on balanced graph and hypergraph designs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7033398)
