Minimum embedding of any Steiner triple system into a 3-sun system via matchings. (English) Zbl 1466.05138
Summary: Let \(G\) be a simple finite graph and \(G^\prime\) be a subgraph of \(G\). A \(G^\prime \)-design \((X, \mathcal{B})\) of order \(n\) is said to be embedded into a \(G\)-design \((X \cup U, \mathcal{C})\) of order \(n + u\), if there is an injective function \(f : \mathcal{B} \to \mathcal{C}\) such that \(B\) is a subgraph of \(f(B)\) for every \(B \in \mathcal{B} \). The function \(f\) is called an embedding of \((X, \mathcal{B})\) into \((X \cup U, \mathcal{C})\). If \(u\) attains the minimum possible value, then \(f\) is a minimum embedding. Here, by means of König’s Line Coloring Theorem and edge coloring properties, some results on the embedding of \(C_k\)-systems into \(k\)-sun systems are obtained and a complete solution to the problem of determining a minimum embedding of any Steiner Triple System into a 3-sun system is given.
MSC:
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
| 05B07 | Triple systems |
References:
| [1] | Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), North Holland · Zbl 1226.05083 |
| [2] | Buratti, M.; Pasotti, A.; Traetta, M., A reduction of the spectrum problem for odd sun systems and the prime case, J. Comb. Des., 29, 5-37 (2020) · Zbl 1536.05107 |
| [3] | Colbourn, C. J., Triple systems, (Colbourn, C. J.; Dinitz, J. H., CRC Handbook of Combinatorial Designs (2007), Chapman and Hall/CRC: Chapman and Hall/CRC Boca Raton, FL), 58-71 · Zbl 1117.05013 |
| [4] | Colbourn, C. J.; Ling, A. C.H.; Quattrocchi, G., Embedding path designs into kite systems, Discrete Math., 297, 38-48 (2005) · Zbl 1082.05013 |
| [5] | Colbourn, C. J.; Ling, A. C.H.; Quattrocchi, G., Minimum embedding of Steiner triple systems into \(( K_4 - e)\)-designs I, Discrete Math., 308, 5308-5311 (2008) · Zbl 1161.05013 |
| [6] | Colbourn, C. J.; Ling, A. C.H.; Quattrocchi, G., Minimum embedding of Steiner triple systems into \(( K_4 - e)\)-designs II, Discrete Math., 309, 400-411 (2009) · Zbl 1161.05015 |
| [7] | Colbourn, C. J.; Quattrocchi, G.; Syrotiuk, V. R., Grooming for two-period optical networks, Networks, 52, 307-324 (2008) · Zbl 1160.68309 |
| [8] | Doyen, J.; Wilson, R. M., Embeddings of Steiner triple systems, Discrete Math., 5, 229-239 (1973) · Zbl 0263.05017 |
| [9] | Fu, C. M.; Jhuang, N. H.; Lin, Y. L.; Lo, S. W.; Sung, H. M., From Steiner triple systems to 3-sun systems, Taiwan. J. Math., 16, 531-543 (2012) · Zbl 1242.05036 |
| [10] | Fu, C. M.; Lin, Y. L.; Lo, S. W.; Hsu, Y. F.; Huang, W. C., The Doyen-Wilson theorem for bull designs, Discrete Math., 313, 498-507 (2013) · Zbl 1259.05026 |
| [11] | Gionfriddo, M.; Quattrocchi, G.; Ragusa, G., Minimum embedding of STSs into \(( K_3 + e)\)-systems, Discrete Math., 313, 1419-1428 (2013) · Zbl 1279.05054 |
| [12] | Lo Faro, G.; Tripodi, A., Embeddings of λ-fold kite systems, \( \lambda \geq 2\), Australas. J. Comb., 36, 143-150 (2006) · Zbl 1115.05011 |
| [13] | Lo Faro, G.; Tripodi, A., The Doyen-Wilson theorem for kite systems, Discrete Math., 306, 2695-2701 (2006) · Zbl 1104.05011 |
| [14] | Lo Faro, G.; Tripodi, A., The Doyen-Wilson theorem for 3-sun systems, Ars Math. Contemp., 16, 119-139 (2019) · Zbl 1416.05049 |
| [15] | Meszka, M.; Rosa, A., Embedding Steiner triple systems into Steiner systems \(S(2, 4, v)\), Discrete Math., 274, 199-212 (2004) · Zbl 1033.05016 |
| [16] | Milici, S., Minimum embedding of \(P_3\)-designs into \(T S(v, \lambda)\), Discrete Math., 308, 331-338 (2008) · Zbl 1131.05017 |
| [17] | Ragusa, G.; Tripodi, A., Minimum embedding of a KS \((u, \lambda)\) into a KS \((u + w, \mu)\), Discrete Math., 312, 195-201 (2012) · Zbl 1238.05172 |
| [18] | Ragusa, G.; Tripodi, A., Minimum embedding of path designs into kite systems, Electron. Notes Discrete Math., 40, 317-321 (2013) |
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.
