\(G\)-designs and related designs. (English) Zbl 0783.05034
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.
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.
Reviewer: D.Fronček
MSC:
| 05B30 | Other designs, configurations |
| 05B05 | Combinatorial aspects of block designs |
| 05C99 | Graph theory |
References:
| [1] | Akiyama, J.; Kano, M., Factors and factorizations of graphs - a survey, J. Graph Theory, 9, 1-42 (1985) · Zbl 0587.05048 |
| [2] | Bermond, J. C.; Sotteau, D., Graph decompositions and \(G\)-designs, (Nash-Williams, C. St. J.A.; Sheehan, J., Proc. 5th British Combinatorial Conf. (1975)), 53-72 · Zbl 0331.05021 |
| [3] | Bermond, J. C.; Huang, C.; Sotteau, D., Balanced cycle and circuit designs: even cases, Ars Combin., 5, 293-318 (1978) · Zbl 0434.05020 |
| [4] | Bermond, J. C.; Thomassen, C., Cycles in digraphs - a survey, J. Graph Theory, 5, 1-43 (1981) · Zbl 0458.05035 |
| [5] | Bermond, J. C.; Heinrich, K.; Yu, M. L., Existence of resolvable path designs, (Alavi, Y.; Chartrand, G.; Mckee, T.; Schwenk, A., Proc. 6th Inter. Conf. The Theory and Applications of Graphs (1988)) · Zbl 0712.05045 |
| [6] | Cain, P., Decomposition of complete graphs into stars, Bull. Austral. Math. Soc., 10, 23-30 (1974) · Zbl 0263.05120 |
| [7] | Cain, P., Decomposition of complete graphs into 6-stars and into 10-stars, (Dold, A.; Eckmann, B., Combinatorial Mathematics 3. Combinatorial Mathematics 3, Lecture Notes in Math., 452 (1975), Springer: Springer Berlin), 136-142 · Zbl 0299.05117 |
| [8] | Cockayne, E. J.; Hartnell, B. L., Edge partitions of complete multipartite graphs into equal length circuits, J. Combin. Theory Ser. B, 23, 174-183 (1977) · Zbl 0313.05121 |
| [9] | Enomoto, H.; Miyamoto, T.; Ushio, K., \(C_k\)-factorization of complete bipartite graphs, Graphs Combin., 4, 111-113 (1988) · Zbl 0673.05071 |
| [10] | Hanani, H., Balanced incomplete block designs and related designs, Discrete Math., 11, 255-369 (1975) · Zbl 0361.62067 |
| [11] | Hell, P.; Rosa, A., Graph decompositions, handcuffed prisoners and balanced \(P\)-designs, Discrete Math., 2, 229-252 (1972) · Zbl 0251.05015 |
| [12] | Hilton, A. J.W., Hamilton decompositions of complete graphs, J. Combin. Theory Ser. B, 36, 125-134 (1984) · Zbl 0542.05044 |
| [13] | Horton, J. D., Resolvable path designs, J. Combin. Theory Ser. A, 117-131 (1985) · Zbl 0584.05056 |
| [14] | Horton, J. D.; Roy, B. K.; Schellenberg, P. J.; Stinson, D. R., On decomposing graphs into isomorphic uniform 2-factors, Ann. Discrete Math., 27, 297-320 (1985) · Zbl 0592.05050 |
| [15] | Huang, C.; Rosa, A., On the existence of balanced bipartite designs, Utilitas Math., 4, 55-75 (1973) · Zbl 0273.05010 |
| [16] | Huang, C., On the existence of balanced bipartite designs II, Discrete Math., 9, 147-159 (1974) · Zbl 0284.05015 |
| [17] | Huang, C., Resolvable balanced bipartite designs, Discrete Math., 14, 319-335 (1976) · Zbl 0325.05008 |
| [18] | Hung, S. H.Y.; Mendelsohn, N. S., Handcuffed designs, Discrete Math., 18, 23-33 (1977) · Zbl 0354.05016 |
| [19] | Kotzig, A., On the decomposition of complete graphs into \(4k\)-gons, Math. Fyz. Casop., 15, 229-233 (1965) · Zbl 0134.43402 |
| [20] | Lawless, J. F., On the construction of handcuffed designs, J. Combin. Theory Ser. A, 16, 76-86 (1974) · Zbl 0275.05009 |
| [21] | Laskar, R.; Auerbach, B., On decomposition of \(r\)-partite graphs into edge-disjoint hamilton circuits, Discrete Math., 14, 265-268 (1976) · Zbl 0322.05128 |
| [22] | Preece, D. A., Balance and designs: another terminological tangle, Utilitas Math, 21C, 85-186 (1982) · Zbl 0499.62064 |
| [23] | Rosa, A., On the cyclic decomposition of the complete graph into \((4m + 2)\)-gons, Math. Fyz. Casop., 16, 349-353 (1966) · Zbl 0147.42803 |
| [24] | Rosa, A., On the cyclic decomposition of the complete graph into polygons with odd number of edges, Časopis Pěst. Mat., 91, 53-63 (1966) · Zbl 0151.33501 |
| [25] | Rosa, A.; Huang, C., Another class of balanced graph designs: balanced circuit designs, Discrete Math., 12, 269-293 (1975) · Zbl 0306.05013 |
| [26] | Sotteau, D., Decomposition of \(K_{m, n}}(K^∗_{m, n }) into cycles (circuits) of length 2k\), J. Combin. Theory Ser. B, 30, 75-81 (1981) · Zbl 0463.05048 |
| [27] | Tarsi, M., Decomposition of complete multigraphs into stars, Discrete Math., 26, 273-278 (1979) · Zbl 0421.05016 |
| [28] | Tarsi, M., Decomposition of a complete multigraph into simple paths: nonbalanced handcuffed designs, J. Combin. Theory Ser. A, 34, 60-70 (1983) · Zbl 0511.05024 |
| [29] | Tazawa, S.; Ushio, K.; Yamamoto, S., Partite-claw-decomposition of a complete multi-partite graph, Hiroshima Math. J., 8, 195-206 (1978) · Zbl 0382.05021 |
| [30] | Tazawa, S., Claw-decomposition and evenly-partite-claw-decomposition of complete multi-partite graphs, Hiroshima Math. J., 9, 503-531 (1979) · Zbl 0419.05016 |
| [31] | Tverberg, H., On the decomposition of \(K_n\) into complete bipartite graphs, J. Graph Theory, 6, 493-494 (1982) · Zbl 0502.05048 |
| [32] | Truszczynski, M., Note on the decomposition of \(λK_{m, n} (λK^∗_{m, n} \)) into paths, Discrete Math., 55, 89-96 (1985) · Zbl 0578.05054 |
| [33] | Ushio, K.; Tazawa, S.; Yamamoto, S., On claw-decomposition of a complete multi-partite graph, Hiroshima Math. J., 8, 207-210 (1978) · Zbl 0382.05022 |
| [34] | Ushio, K., Bipartite decomposition of complete multipartite graphs, Hiroshima Math. J., 11, 321-345 (1981) · Zbl 0482.05051 |
| [35] | Ushio, K., On balanced claw designs of complete multi-partite graphs, Discrete Math., 38, 117-119 (1982) · Zbl 0475.05022 |
| [36] | Ushio, K., \(P_3\)-factorization of complete bipartite graphs, Discrete Math., 72, 361-366 (1988) · Zbl 0667.05045 |
| [37] | Wilson, R. M., Decompositions of complete graphs into subgraphs isomorphic to a given graph, (Nash-Williams, C. St. J.A.; Sheehan, J., Proc. 5th British Combinatorial Conf. (1975)), 647-659 · Zbl 0322.05116 |
| [38] | Yamamoto, S.; Ikeda, H.; Shige-eda, S.; Ushio, K.; Hamada, N., On claw-decomposition of complete graphs and complete bigraphs, Hiroshima Math. J., 5, 33-42 (1975) · Zbl 0297.05143 |
| [39] | Yamamoto, S.; Ikeda, H.; Shige-eda, S.; Ushio, K.; Hamada, N., Design of a new balanced file organization scheme with the least redundancy, Inform. and Control, 28, 156-175 (1975) · Zbl 0309.68034 |
| [40] | Yamamoto, S.; Tazawa, S.; Ushio, K.; Ikeda, H., Design of a generalized balanced multiple-valued file organization scheme of order two, (Lowenthal, E.; Dale, N. B., Proc. ACM-SIGMOD Inter. Conf. on Management of Data (1978)), 47-51 |
| [41] | Yamamoto, S.; Tazawa, S.; Ushio, K.; Ikeda, H., Design of a balanced multiple-valued file organization scheme with the least redundancy, ACM Trans. Database Systems, 4, 518-530 (1979) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
