On the existence of maximum resolvable (\(K_{4} - e\))-packings. (English) Zbl 1236.05060
Summary: Suppose \(K_v\) is the complete undirected graph with \(v\) vertices and \(G\) is a finite simple undirected graph without isolated vertices. A \(G\)-packing of \(K_v\) is a pair \((X,{\mathcal{B}})\), where \(X\) is the vertex set of \(K_v\) and \({\mathcal{B}}\) is a collection of edge-disjoint subgraphs (blocks) isomorphic to \(G\) in \(K_v\). A \(G\)-packing \((X,{\mathcal{B}})\) is called resolvable if \({\mathcal{B}}\) can be partitioned into parallel classes such that every vertex is contained in precisely one block of each class. Let \((v, G,1)\)-MRP denote a resolvable \(G\)-packing containing the maximum possible number \(r(v,G)\) of parallel classes. Suppose \(e(G)\) and \(V(G)\) are the number of edges and the vertex set of the graph \(G\), respectively. Let \(k= |V(G)|\). Clearly, \(v\equiv 0 \pmod k\) and \(r(v,G) \leq \lfloor k(v- 1)/2e(G) \rfloor\) for a \((v,G,1)\)-MRP. Let \(K_4- e\) be the graph obtained from a \(K_4\) by removing one edge. It is proved in this paper that there exists a \((v,K_4- e,1)\)-MRP with \(\lfloor 2(v- 1)/5\rfloor\) parallel classes if and only if \(v\equiv 0\pmod 4\) with the possible exceptions of \(v= 12,\) 116, 132, 172, 232, 280, 292, 296, 372, 412, 532, 592, 612.
MSC:
| 05B40 | Combinatorial aspects of packing and covering |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
References:
| [1] | Baker, R.; Wilson, R. M., Nearly Kirkman triple systems, Utilitas Math., 11, 289-296 (1977) · Zbl 0362.05030 |
| [2] | Bermond, J. C.; Schönheim, J., \(G\)-decompositions of \(K_n\), where \(G\) has four vertices or less, Discrete Math., 19, 113-120 (1977) · Zbl 0376.05016 |
| [3] | Brouwer, A., Two new Kirkman triple systems, Utilitas Math., 13, 311-314 (1978) · Zbl 0379.05008 |
| [4] | Brouwer, A., Optimal packing of \(K_4^\prime\) s into a \(K_n\), J. Combin. Theory Ser. A, 26, 278-297 (1979) · Zbl 0412.05030 |
| [5] | (Colbourn, C. J.; Dinitz, J. H., The CRC Handbook of Combinatorial Designs (2006), Chapman and Hall/CRC: Chapman and Hall/CRC Boca Raton, FL) · Zbl 1101.05001 |
| [6] | Colbourn, C. J.; Stinson, D. R.; Zhu, L., More frames with block size four, J Combin. Math. Combin. Comput., 23, 3-20 (1997) · Zbl 0879.05016 |
| [7] | Furino, S. C.; Miao, Y.; Yin, J. X., Frames and Resolvable Designs: Uses, Constructions and Existence (1996), CRC Press: CRC Press Boca Raton, FL · Zbl 0855.62061 |
| [8] | Ge, G.; Lam, C. W.H.; Ling, A. C.H.; Shen, H., Resolvable maximum packings with quadruples, Des. Codes Cryptogr., 35, 287-302 (2005) · Zbl 1066.05046 |
| [9] | Ge, G.; Ling, A. C.H., On the existence of resolvable \((K_4 - e)\)-designs, J. Combin. Des., 15, 502-510 (2007) · Zbl 1128.05002 |
| [10] | Ge, G.; Ling, A. C.H., Asymptotic results on the existence of 4-RGDDs and uniform 5-GDDs, J. Combin. Des., 13, 222-237 (2005) · Zbl 1062.05023 |
| [11] | Hoffman, D. G.; Lindner, C. C.; Sharry, M. J.; Street, A. P., Maximan packings of \(K_n\) with copies of \(K_4 - e\), Aequationes Math., 51, 247-269 (1996) · Zbl 0851.05034 |
| [12] | A. Kotzig, A. Rosa, Nearly Kirkman triple systems, Proceedings of the Fifth SE Conference on combinatorics, Graph Theory and Computing, Boca Ratan, FL, 1974, pp. 607-614; A. Kotzig, A. Rosa, Nearly Kirkman triple systems, Proceedings of the Fifth SE Conference on combinatorics, Graph Theory and Computing, Boca Ratan, FL, 1974, pp. 607-614 · Zbl 0311.05023 |
| [13] | Mullin, R. C.; Ling, A. C.H.; Able, R. J.R.; Bennett, F. E., On the closure of subsets of \(\{4, 5, \ldots, 9 \}\) which contain \(\{4 \}\), Ars Combin., 45, 33-76 (1997) · Zbl 0933.05008 |
| [14] | Ray-Chaudhuri, D. R.; Wilson, R. M., Solution of Kirkman’s schoolgirl problem, Amer. Math. Soc. Symp. Pure. Math., 19, 187-204 (1971) · Zbl 0248.05009 |
| [15] | Rees, R.; Stinson, D., On resolvable group-divisible designs with block size 3, Ars Combin., 23, 107-120 (1987) · Zbl 0621.05004 |
| [16] | Roditty, Y., Packings and coverings of the complete graph I: The forests of order five Internat, J. Math. Math. Sci., 9, 277-282 (1986) · Zbl 0608.05028 |
| [17] | Schönheim, J., On maximum systems of \(k\)-tuples, Studia Sci. Math. Hungar., 1, 363-368 (1966) · Zbl 0146.01403 |
| [18] | Stanton, R. G.; Rogers, M. J., Packings and coverings by triples, Ars Combin., 13, 61-69 (1982) · Zbl 0501.05023 |
| [19] | Zhang, S.; Yin, J., Packing of \(K_v\) with graphs of five vertices, J. Statist. Plann. Inferernce, 106, 387-408 (2002) · Zbl 1002.05055 |
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.
