Isomorphic path decompositions of crowns. (English) Zbl 1071.05563

Shyu, Tay-Woei; Lin, Chiang

Ars Comb. 67, 97-103 (2003).

The crown \(C_{n, k}\) for positive integers \(n, k\) is the graph with the vertex set \(\{a_1, \dots , a_n, b_1, \dots , b_n\}\) whose edge set consists of edges \(a_i b_j\), where \(1 \leq i \leq n\) and \(j\) is congruent modulo \(n\) to an integer between \(i\) and \(i + k - 1\). The decomposition of a crown \(C_{n, k}\) into paths \(P_l\) of length \(l\) for given positive integers \(n, k, l\) is studied. The main theorem states a necessary and sufficient condition for the existence of such a decomposition.

Reviewer: Bohdan Zelinka (Liberec)

MSC:

05C70

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