Separating subgraphs in k-trees: Cables and caterpillars (Q795842)

The class of k-trees has been defined recursively by starting with a \(k+1\)-clique and successively adding one new vertex joined to an existing k-clique. Ordinary trees are 1-trees. The author extends various concepts such as paths and caterpillars from ordinary trees to k-trees. He finds that the union of all cliques that separate u from v comprise a k-1- caterpillar with additional restrictions. Since k-trees are k-connected, he calls the union of k vertex disjoint paths from u to v a u,v-cable. The cable distance is the ''length'' of a shortest cable. The shortest cable is found to be unique and induced by the caterpillar mentioned above. A sufficient condition is given to demonstrate that cable distance may exceed ordinary distance.