zbMATH — the first resource for mathematics

Isomorphic path decompositions of crowns. (English) Zbl 1071.05563
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.

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