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