scientific article; zbMATH DE number 17515
[For the entire collection see Zbl 0726.00009.] Let \(G\) be a simple graph without isolated vertices. A graph \(H\) is said to be \(G\)-decomposable (or admit a \(G\)-decomposition), denoted by \(H\to G\), if the edges of \(H\) can be partitioned into edges of subgraphs isomorphic to \(G\). A \(G\)-design is a \(G\)-decomposition of \(K_ n\), the complete graph with \(n\) vertices. If \(G\) is \(K_ k\), a \(G\)-design \(K_ n\to G\) is nothing more than a \((n,k,1)\)-BIBD (balanced incomplete block design). \(G\)-designs can also be defined by using the concept of \(G\)- blocks, similar to the corresponding definition of a BIBD (see \textit{H. Hanani} [Discrete Math. 11, 255-369 (1975; Zbl 0361.62067)]). Simple calculation shows that if \(K_ n\to G\) then \[ \text{(i) } n\geq k\quad \text{(ii) } n(n-1)\equiv 0\pmod{2e}\quad\text{(iii) } n-1\equiv 0\pmod f \tag{1.1} \] where \(G\) is a graph with \(k\) vertices and \(e\) edges and \(f\) is the greatest common divisor of the degrees of the vertices of \(G\). The conditions for the existence of a \(G\)-design have been studied extensively (for example see \textit{J.-C. Bermond} and \textit{D. Sotteau} [Proc. 5th Br. Comb. Conf., Aberdeen 1975, 53-72 (1976; Zbl 0331.05021)]). The case when \(G\) is of at most four vertices has been solved completely in \textit{J.-C. Bermond} and \textit{J. Schönheim} [Discrete Math. 19, 113-120 (1977; Zbl 0376.05016)]. For graphs with five vertices, an almost complete solution has been given in \textit{J.-C. Bermond}, \textit{C. Huang}, \textit{A. Rosa} and \textit{D. Sotteau} [Ars. Comb. 10, 211-254 (1980; Zbl 0454.05053)]. In this paper we consider the case when \(G\) is of six vertices and \(e\) edges, where \(3\leq e\leq 6\). As we see in Figure 1, there are 28 non- isomorphic graphs which need to be considered. It will be shown that the necessary condition in (1.1) for the existence of \(G\)-designs for these graphs is also sufficient with five exceptions for which \(G\)-designs do not exist.
- On colored designs. I
- \(G\)-designs and related designs
- Decomposition of complete multigraphs into crown graphs
- Decompositions of \(\lambda K_v\)
- Graph designs for all graphs with six vertices and eight edges
- The proportion of various graphs in graph-designs
- Loop designs
- Graph designs for a nine-edge six-vertex graph
- Constructions of optimal packing and covering of the complete multigraph with applications
- scientific article; zbMATH DE number 5139440 (Why is no real title available?)
- G-design of -fold complete multipartite graph where G is three kinds of graphs with five points
- A survey on the existence ofG-Designs
- The existence of \((K_2\times K_6)\)-designs
- On the existence of k-sun systems
- scientific article; zbMATH DE number 1792569 (Why is no real title available?)
- scientific article; zbMATH DE number 898424 (Why is no real title available?)
- Decomposition of complete graphs into connected unicyclic bipartite graphs with eight edges
- The Doyen-Wilson theorem for 3-sun systems
- Reaction graphs of the K₄-e design of order 6
- scientific article; zbMATH DE number 2219717 (Why is no real title available?)
- G-designs for the connected triangular bicyclic graphs with nine edges
- Decomposition of complete graphs into forests with six edges
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3974839)
