Decomposition of Complete, Complete Bipartite, and Complete Tripartite Graphs into Half-Sunlet Graphs of Order Twelve

Source abstract

The half-sunlet graph HS3k is a 2k-cycle with a pendant edge at every alternate vertex (|V|=|E|=3k). We give a complete decomposition theory for HS12 (k=4), characterising when HS12 decomposes G for G complete, complete bipartite, and complete tripartite. Writing m=min(a,b) and M=max(a,b), we prove the following. First, HS12∣Ka if and only if a≥16 and a≡0,1,9,16(mod24). Second, HS12∣Ka,b if and only if m≥4, M≥8 and 12 divides ab, with the single exception of the family in which m=6, M is even and 3 does not divide M, for which no decomposition exists. Third, HS12∣Ka,b,c if and only if 12 divides ab+bc+ca and the multiset {a,b,c} is none of {2,2,c}, {1,4,c} with c≡4(mod12), {1,6,6} and {2,3,6}. The three hosts thus exhibit a structural gradient: the complete graph admits a purely arithmetic criterion with no exceptions, whereas the bipartite and tripartite hosts admit one and four exceptional families, respectively.