\((G_m,H_m)\)-multifactorization of \(\lambda K_m\). (English) Zbl 1195.05061

Priyadharsini, H. M.; Muthusamy, A.

J. Comb. Math. Comb. Comput. 69, 145-150 (2009).

Summary: A \((G,H)\)-multifactorization of \(\lambda K_m\) is a partition of the edge set of \(\lambda K_m\) into \(G\)-factors and \(H\)-factors with at least one \(G\)-factor and one \(H\)-factor. Atif Abueida and Theresa O’. Neil [“Multidecomposition of \(\lambda K_m\) into small cycles and claws”, Bull. Inst. Comb. Appl. 49, 32–40 (2007; Zbl 1112.05084)] have conjectured that for any integer \(n\geq 3\) and \(m\geq n\), there is a \((G_n,H_n)\)-multidecomposition of \(\lambda K_m\) where \(G_n= K_{1,n-1}\) and \(H_n= C_n\). In this paper it is shown that the above conjecture is true for \(m=n\) when

(i)

\(G_m=K_{1,m-1}\); \(H_m=K_m\),

(ii)

\(G_m= H_{1,m-1}\); \(H_m= P_m\) and

(iii)

\(G_m= P_m\); \(H_m= C_m\).

MSC:

05C70

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Keywords:

multifactorization; multidecomposition; stars; paths; cycles