Journal of Integer Sequences, Vol. 25 (2022), Article 22.5.6

How to Count k-Paths

Allan Bickle
Department of Mathematics
Penn State Altoona
3000 Ivyside Park
Altoona, PA 16601


A k-tree is a graph that can be formed by starting with the complete graph Kk and iterating the operation of making a new vertex adjacent to all the vertices of a k-clique of the existing graph. For order n > k + 1, a k-path graph is a k-tree with exactly two vertices of degree k. We develop a formula for the number of unlabeled k-paths of order n. In particular, there is a bijection between these graphs and equivalence classes of strings of numbers from {1,2,...,k} under a relation that treats them as equivalent when they can be made the same by permutation of their numbers and possible reversal of the string.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000085 A001998 A005418 A056323 A056324 A056325 A103293 A345207.)

Received June 11 2021; revised versions received June 17 2021; March 28 2022; April 2 2022. Published in Journal of Integer Sequences, June 21 2022.

Return to Journal of Integer Sequences home page