Factorizations of Complete Graphs into\( \{r,s,2,2\} \)-Caterpillars of Diameter 5

Michael Kubesa1
1Technical University Ostrava

Abstract

A caterpillar \( R \) is a tree with the property that after deleting all vertices of degree 1, we obtain a path \( P \) or a single vertex. The path \( P \) is called the spine of caterpillar \( R \). If the spine has length 3 and \( R \) contains vertices of degrees \( r, s, 2, 2 \), where \( r, s > 2 \), then we say that \( R \) is a \( \{r, s, 2, 2\} \)-caterpillar of diameter 5. We completely characterize \( \{r, s, 2, 2\} \)-caterpillars of diameter 5 on \( 4k + 2 \) vertices that factorize \( K_{4k+2} \).

Keywords: Decompositions and factorizations of a complete graphs, spanning trees, blended p-labeling, caterpillars.