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
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