Uniformly resolvable $(C_4, K_{1,3})$-designs of order v and

Mario Gionfriddo, Selda Kucukcifci, Salvatore Milici, E Sule Yazici

Abstract


In this paper we consider the uniformly resolvable decompositions of the complete graph $\lambda K_v$ into subgraphs where each resolution class contains only blocks isomorphic to the same graph. We consider the cases in which all the resolution classes are either $C_4$ or $K_{1,3}$. We prove that this type of system does not exist for $\lambda$ odd and determine completely the spectrum for $\lambda=2$.

Keywords


Design Theory;Resolvable graph decomposition; Uniform resolutions;

Full Text:

PDF

References


P. Adams, E. Billington, D. Bryant, and S. El-Zanati, On the Hamilton-Waterloo problem, Graphs Combin. 18 (2002), 31-51.

B. Alspach, P. J. Shellenberg, D. R. Stinson, and D.Wagner, The Oberwolfach problem and factors of uniform length, J. Combin. Theory Ser. A 52 (1989), 20-43.

L. Berardi, M. Gionfriddo, and R. Rota, Balanced and strongly balanced Pk-designs, Discrete Math. 312 (2012), 633-636.

D. Bryant and P. Danziger, On bipartite 2-factorizations of K_n-I and the Oberwolfach problem, J. Graph Theory 68 (2011), 22-37.

D. Bryant, P. Danziger, and W. Pettersson, Bipartite 2-factorizations of complete multipartite graphs, J. Graph Theory 78 (2015), 287-294.

D. Bryant and V. Scharaschkin, Complete solutions to the Oberwolfach problem for an infinite set of orders, J. Combin. Theory Ser. B 78 (2009), 904-918.

C. J. Colbourn and J. H. Dinitz, The CRC Handbook of Combinatorial Designs, Chapman and Hall/CRC, Boca Raton, FL, 2007, Online updates www.emba.uvm.edu/~dinitz/newresults.html.

P. Danziger, G. Quattrocchi, and B. Stevens, The Hamilton-Waterloo problem for cycle sizes 3 and 4, J. Combin. Des. 12 (2004), 221-232.

J. H. Dinitz and A. C. H. Ling, The Hamilton-Waterloo problem: The case of triangle-factors and one Hamilton cycle, J. Combin. Des. 17 (2009), no. 2, 160-176.

J. H. Dinitz, A. C. H. Ling, and P. Danziger, Maximum uniformly resolvable designs with block sizes 2 and 4, Discrete Math. 309 (2009), 4716-4721.

M. Gionfriddo, S. S. Kucukcifci, and L. Milazzo, Balanced and strongly balanced 4-kite designs, Util. Math. 91 (2013), 121-129.

M. Gionfriddo, L. Milazzo, and V. Voloshin, Hypergraphs and Designs, Mathematics Research Developments, Nova Science Publishers Inc, 2014.

M. Gionfriddo and S. Milici, On the existence of uniformly resolvable decompositions of k_v and k_v-i into paths and kites, Discrete Math. 313 (2013), 2830-2834.

M. Gionfriddo and S. Milici, Uniformly resolvable H-designs with H = {P_3, P_4}; P_4, Australas. J. Combin. 60 (2014), no. 3, 325-332.

M. Gionfriddo and S. Milici, Uniformly resolvable {K_2,P_k}-designs with k = {3, 4}, Contr. Discrete Math. 10 (2015), no. 1, 126-133.

P. Horak, R. Nedela, and A. Rosa, The Hamilton-Waterloo problem: the case of Hamilton factors and triangle-factors, Discrete Math. 284 (2004), 181-188.

E. Kohler, Das Oberwolfacher problem, Mitt. Math. Gesellsch. Hamburg 10 (1973), 124-129.

S. Kucukcifci, G. Lo Faro, S. Milici, and A. Tripodi, Resolvable 3-star designs, Discrete Math. 338 (2015), 608-614.

S. Kucukcifci, S. Milici, and Zs. Tuza, Maximum uniformly resolvable decompositions of k_v into 3-stars and 3-cycles, Discrete Math. 338 (2015), 1667-1673.

J. Liu, The equipartite Oberwolfach problem with uniform tables, J. Combin. Theory Ser. A 101 (2003), 20-34.

J. Liu and D. R. Lick, On lambda-fold equipartite Oberwolfach problem with uniform table sizes, Ann. Combin. 7 (2003), 315-323.

S. Milici, A note on uniformly resolvable decompositions of K_v and K_v-I into 2-stars and 4-cycles, Australas. J. Combin. 56 (2013), 195-200.

S. Milici and Zs. Tuza, Uniformly resolvable decompositions of K_v into P_3 and K_3 graphs, Discrete Math. 331 (2014), 137-141.

W. L. Piotrowski, The solution of the bipartite analogue of the Oberwolfach problem, Discrete Math. 97 (1991), 339-356.

R. Rees, Uniformly resolvable pairwise balanced designs with block sizes two and three, J. Combin. Theory Ser. A 45 (1987), 207-225.

E. Schuster, Uniformly resolvable designs with index one and block sizes three and five and up to five with blocks of size five, Discrete Math. 309 (2009), 4435-4442.

E. Schuster, Uniformly resolvable designs with index one and block sizes three and four-with three or five parallel classes of block size four, Discrete Math. 309 (2009), 2452-2465.

E. Schuster, Small uniformly resolvable designs for block sizes 3 and 4, J. Combin. Des. 21 (2013), 481-523.

E. Schuster and G. Ge, On uniformly resolvable designs with block sizes 3 and 4, Des. Codes Cryptogr. 57 (2010), 47-69.

T. Traetta, A complete solution to the two-table Oberwolfach problems, J. Combin. Theory Ser. A. 120 (2013), 984-997.


Comments on this article

View all comments


Contributions to Discrete Mathematics. ISSN: 1715-0868