##
**
How to Count ***k*-Paths

###
Allan Bickle

Department of Mathematics

Penn State Altoona

3000 Ivyside Park

Altoona, PA 16601

USA

**Abstract:**

A *k*-tree is a graph that can be formed by starting with
the complete graph
*K*_{k} 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**