×

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

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.)

Citations:

Zbl 1112.05084