Cyclic clique decompositions of powerof cycles

Abstract

A clique decomposition P of a graph G is a collection of cliques of G such that each edge of G belongs to exactly one clique in the collection. We say that P is cyclic if there is an isomorphism : V (G)→ V (G) such that Kk{α (v₁), α (v₂), α (v₃), ... , α (vk)g is a clique in P whenever Kk{v₁; v₂; v₃; :::; vk} is. The k-power of an n-cycle, Ck n, is the graph having the same vertex set as Cn and uv is an edge in Ck n if and only if dCn(u; v) ≤ k. Partly inspired by the solution of Heffter’s difference problem, we introduce a certain construction of cyclic clique decompositions of the k-power of an n-cycle. Finally, we establish an optimal cyclic clique decomposition into cliques of order at most 4 for each 3 ≤ k ≤ 26 and all natural numbers n > 3k.