Constructing the spectrum of packings and coverings for the complete graph with stars with up to five edges. (English) Zbl 1339.05305
Summary: The packing and covering problems have been considered for several classes of graphs. For instance, D. Bryant and D. Horsley [J. Comb. Theory, Ser. B 98, No. 5, 1014–1037 (2008; Zbl 1162.05037)] have investigated the packing problem for paths and cycles, and the packing and covering problems for 3-cubes. The packing and covering problems were settled for stars with up to six edges by Y. Roditty [J. Comb. Theory, Ser. A 35, 213–243 (1983; Zbl 0521.05053); Int. J. Math. Math. Sci. 9, 277–282 (1986; Zbl 0608.05028); Ars Comb. 19, 81–93 (1985; Zbl 0578.05013); Ars Comb. 35, 33–64 (1993; Zbl 0796.05074)]. In this paper, for every possible leave graph (excess graph), we find a corresponding maximum packing (minimum covering) of the complete graph with stars with up to five edges.
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
References:
| [1] | Adams, P., Bryant, D., Buchanan, M.: A survey on the existence of \[G\] G-designs. J. Combin. Des. 16, 373-410 (2008) · Zbl 1168.05303 · doi:10.1002/jcd.20170 |
| [2] | Adams, P., Bryant, D., El-Zanati, S.: Packing and covering the complete graph with cubes. Aust. J. Combin. 20, 267288 (1999) · Zbl 0980.05042 |
| [3] | Bryant, D.: Packing paths in complete graphs. J. Combin. Theory Ser. B 100(2), 206215 (2010) · Zbl 1216.05111 |
| [4] | Bryant, D., Horsley, D.: Packing cycles in complete graphs. J. Combin. Theory Ser. B 98(5), 10141037 (2008) · Zbl 1162.05037 |
| [5] | Colbourn, C., Dinitz, J.: The CRC Handbook of Combinatorial Designs (Second Edition), Chapter 24. CRC Press, Boca Raton (2007) · Zbl 1101.05001 |
| [6] | Dyer, D., Haghshenas, S., Shalaby, N.: Constructing the spectrum of packings and coverings for the complete graph with \[44\]-stars. J. Combin. Math. Combin. Comput. (to appear) · Zbl 1341.05153 |
| [7] | Hell, P., Rosa, A.: Graph decompositions, handcuffed prisoners and balanced \[PP\]-designs. Discrete Math. 2(3), 229-252 (1972) · Zbl 0251.05015 · doi:10.1016/0012-365X(72)90005-2 |
| [8] | Hoffman, D.G., Roberts, D.: Maximum packings of \[K_n\] Kn with \[k\] k-stars. Aust. J. Combin. 59, 206-210 (2014) · Zbl 1296.05164 |
| [9] | Huang, C., Rosa, A.: Decomposition of complete graphs into trees. Ars Combin. 5, 23-63 (1978) · Zbl 0418.05041 |
| [10] | Roditty, Y.: Packing and covering of the complete graph with a graph \[G\] G of four vertices or less. J. Combin. Theory Ser. B 34(2), 231-243 (1983) · Zbl 0521.05053 · doi:10.1016/0097-3165(83)90058-4 |
| [11] | Roditty, Y.: Packing and covering of the complete graph. II. The trees of order six. Ars Combin. 19, 81-93 (1985) · Zbl 0578.05013 |
| [12] | Roditty, Y.: The packing and covering of the complete graph. I. The forests of order five. Int. J. Math. Math. Sci. 9(2), 277-282 (1986) · Zbl 0608.05028 · doi:10.1155/S0161171286000340 |
| [13] | Roditty, Y.: Packing and covering of the complete graph. IV. The trees of order seven. Ars Combin. 35, 33-64 (1993) · Zbl 0796.05074 |
| [14] | Tarsi, M.: Decomposition of complete multigraphs into stars. Discrete Math. 26, 273-278 (1979) · Zbl 0421.05016 · doi:10.1016/0012-365X(79)90034-7 |
| [15] | Tarsi, M.: Decomposition of a complete multigraph into simple paths: nonbalanced handcuffed designs. J. Combin. Theory Ser. A 34(1), 6070 (1983) · Zbl 0511.05024 |
| [16] | West, D.: Introduction to Graph Theory, 2nd edn. Prentice Hall, Upper Saddle River (2001) |
| [17] | Wilson, R.: Decompositions of complete graphs into subgraphs isomorphic to a given graph. Congr. Numer. 15, 647-659 (1976) · Zbl 0322.05116 |
| [18] | Yamamoto, S., Ikedo, H., Shige-eda, S., Ushio, K., Hamada, N.: On claw-decompositions of complete graphs and complete bigraphs. Hiroshima Math. J. 5, 33-42 (1975) · Zbl 0297.05143 |
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.
