Embedding path designs into kite systems. (English) Zbl 1082.05013
A kite is a graph on four vertices consisting of a triangle with an attached edge. A kite design of order \(n\) is a decomposition of the edge-set of the complete graph \(K_n\) on \(n\) vertices into kites. J. C. Bermond and J. Schönheim [Discrete Math.19, 113–120 (1977; Zbl 0376.05016)] proved that a kite design of order \(n\) exists if and only if \(n \equiv 0\) or \(1 \pmod{8}\). A path design of order \(v\) and block size 3, denoted by \(P(v,3,1)\) is a decomposition of the edge-set of \(K_v\) into simple paths of length 2, that is, simple paths with three vertices and two edges. An embedding of a \(P(v,3,1)\) in a kite design, whose vertex set strictly contains the vertex set of the \(P(v,3,1)\), is an injection \(f\) from the set of paths of the \(P(v,3,1)\) into the set of kites of the kite design, such that, for each path \(B\) of the \(P(v,3,1)\), \(B\) is an induced subgraph of \(f(B)\). For each \(n \equiv 0\) or \(1 \pmod{8}\), the authors determine the set of all integers \(v\) for which there is a non-trivial \(P(v,3,1)\) embedded in a kite design of order \(n\).
Reviewer: Luc Teirlinck (Auburn)
MSC:
| 05B05 | Combinatorial aspects of block designs |
Keywords:
kite designCitations:
Zbl 0376.05016References:
| [1] | Bermond, J. C.; Ceroi, S., Minimizing SONET ADMs in unidirectional WDM rings with grooming ratio 3, Networks, 41, 83-86 (2003) · Zbl 1014.05051 |
| [2] | J.-C. Bermond, C.J. Colbourn, D. Coudert, G. Ge, A.C.H. Ling, X. Muñoz, Traffic grooming in unidirectional WDM rings with grooming ratio \(C = 6\), SIAM J. Discrete Math., to appear.; J.-C. Bermond, C.J. Colbourn, D. Coudert, G. Ge, A.C.H. Ling, X. Muñoz, Traffic grooming in unidirectional WDM rings with grooming ratio \(C = 6\), SIAM J. Discrete Math., to appear. · Zbl 1092.68003 |
| [3] | Bermond, J. C.; Colbourn, C. J.; Ling, A. C.H.; Yu, M. L., Grooming in unidirectional rings \(K_4 - e\) designs, Discrete Math., 284, 57-62 (2004) · Zbl 1061.90017 |
| [4] | J.C. Bermond, D. Coudert, Traffic grooming in unidirectional WDM ring networks using design theory, Proceedings ICC 2003, IEEE International Conference on Communications, 11-15 May 2003.; J.C. Bermond, D. Coudert, Traffic grooming in unidirectional WDM ring networks using design theory, Proceedings ICC 2003, IEEE International Conference on Communications, 11-15 May 2003. |
| [5] | J.C. Bermond, D. Coudert, X. Muñoz, Traffic grooming in unidirectional WDM ring networks: the all-to-all unitary case, Proceedings of the ONDM03, Seventh IFIP Workshop Optical Network Design and Modelling, Budapest, February 2003, pp. 1135-1153.; J.C. Bermond, D. Coudert, X. Muñoz, Traffic grooming in unidirectional WDM ring networks: the all-to-all unitary case, Proceedings of the ONDM03, Seventh IFIP Workshop Optical Network Design and Modelling, Budapest, February 2003, pp. 1135-1153. |
| [6] | Bermond, J. C.; Schönheim, J., \(G\)-decomposition of \(K_n\), where \(G\) has four vertices or less, Discrete Math., 19, 113-120 (1977) · Zbl 0376.05016 |
| [7] | Colbourn, C. J.; Dinitz, J. H., CRC Handbook of Combinatorial Designs (1996), CRC Press: CRC Press Boca Raton, FL · Zbl 0836.00010 |
| [8] | C.J. Colbourn, G. Quattrocchi, V.R. Syrotiuk, Embedding problems and optical networks, in preparation.; C.J. Colbourn, G. Quattrocchi, V.R. Syrotiuk, Embedding problems and optical networks, in preparation. · Zbl 1160.68309 |
| [9] | Dinitz, J. H.; Stinson, D. R., Contemporary Design Theory—A Collection of Surveys (1992), Wiley: Wiley New York · Zbl 0746.00028 |
| [10] | L. Gionfriddo, C.C. Lindner, Nesting kite and 4-cycle systems, Australasian J. Combin., to appear.; L. Gionfriddo, C.C. Lindner, Nesting kite and 4-cycle systems, Australasian J. Combin., to appear. · Zbl 1077.05022 |
| [11] | Hell, P.; Rosa, A., Graph decompositions, handcuffed prisoners, and balanced \(P\)-designs, Discrete Math., 2, 229-252 (1972) · Zbl 0251.05015 |
| [12] | Hung, S. H.Y.; Mendelsohn, N. S., Handcuffed designs, Aequationes Math., 18, 256-266 (1974) · Zbl 0296.05011 |
| [13] | Küçükçifçi, S.; Lindner, C. C., The metamorphosis of \(\lambda \)-fold block designs with block size four into \(\lambda \)-fold kite systems, JCMCC, 40, 241-252 (2002) · Zbl 1001.05021 |
| [14] | G. Lo Faro, A. Tripodi, The Doyen-Wilson theorem for kite systems, preprint.; G. Lo Faro, A. Tripodi, The Doyen-Wilson theorem for kite systems, preprint. · Zbl 1104.05011 |
| [15] | Milici, S.; Quattrocchi, G., Embedding handcuffed designs with block size 2 or 3 in 4-cycle systems, Discrete Math., 208/209, 443-449 (1999) · Zbl 0930.05009 |
| [16] | Quattrocchi, G., Embedding path designs in 4-cycle systems, Discrete Math., 255, 349-356 (2002) · Zbl 1007.05035 |
| [17] | Quattrocchi, G., Embedding handcuffed designs in \(D\)-designs, where \(D\) is the triangle with an attached edge, Discrete Math., 261, 413-434 (2003) · Zbl 1019.05012 |
| [18] | Tarsi, M., Decomposition of a complete multigraph into simple pathsnonbalanced handcuffed designs, J. Combin. Theory Ser. A, 34, 60-70 (1983) · Zbl 0511.05024 |
| [19] | H. Wang, Y. Chang, Kite-group divisible designs of type \(g^t u^1\), preprint.; H. Wang, Y. Chang, Kite-group divisible designs of type \(g^t u^1\), preprint. · Zbl 1117.05011 |
| [20] | H. Wang, Y. Chang, \(( K_3 + e, \operatorname{\Lambda;})\)-group divisible designs of type \(g^t u^1\), preprint.; H. Wang, Y. Chang, \(( K_3 + e, \operatorname{\Lambda;})\)-group divisible designs of type \(g^t u^1\), preprint. · Zbl 1224.05340 |
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.
