\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}
\usepackage{lineno}
\usepackage{setspace}
\usepackage{tikz}
\usepackage{tkz-graph}
\usepackage{tkz-berge}
\usepackage{multicol}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf How to Count $k$-Paths
}
\vskip 1cm
\large
Allan Bickle\\
Department of Mathematics\\
Penn State Altoona\\
3000 Ivyside Park \\
Altoona, PA 16601 \\
USA \\
\href{mailto:aub742@psu.edu}{\tt aub742@psu.edu} \\
\end{center}
\vskip .2 in
\begin{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 $\left\{ 1,2,\ldots,k\right\} $
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.
\end{abstract}
\section{Introduction}
In this paper, we seek to count the number of unlabeled $k$-paths
of order $n$. This work builds on previous papers on maximal $k$-degenerate
graphs with diameter 2~\cite{Bickle 2021} and $k$-paths of $k$-trees
\cite{Bickle 2020-1}.
Undefined notation and terminology will follow Bickle~\cite{Bickle 2020}.
In particular, $K_{n}$ is the complete graph with $n$ vertices,
and $P_{n}$ is the path with $n$ vertices. The complement of a graph
$G$ is denoted $\overline{G}$, and the join of two graphs $G$ and
$H$ is denoted $G+H$. The neighborhood of a vertex $v$ is denoted
$N(v)$.
\begin{definition}
A \textit{$k$-tree} is a graph that can be formed by starting with
$K_{k}$ and iterating the operation of making a new vertex adjacent
to all the vertices of a $k$-clique of the existing graph.
A \textit{$k$-leaf} is a degree $k$ vertex of a $k$-tree.
A \textit{$k$-path graph} $G$ is an alternating sequence of distinct
$k$-cliques and $k+1$-cliques $e_{0},t_{1},e_{1},t_{2}, \ldots,t_{p},e_{p}$,
starting and ending with a $k$-clique and such that $t_{i}$ contains
exactly two $k$-cliques $e_{i-1}$ and $e_{i}$.
An \textit{interior $k$-caterpillar} is a $k$-tree so that there
is some $k$-path such that the $k$-leaves of the caterpillar are
$k$-leaves of the path or are attached to interior $k$-cliques (the
$t_{i}$'s) of the $k$-path.
A \textit{dominating vertex} of a graph is a vertex adjacent to all
other vertices.
\end{definition}
Any $k$-path is a $k$-tree. An example of a 2-path is shown below.
\begin{figure}[h]
\begin{centering}
\begin{tikzpicture}
\SetVertexSimple[Shape=circle, MinSize=8pt, FillColor=white!50]
\Vertex[x=0,y=0]{00}
\Vertex[x=.5,y=-.86]{a}
\Vertex[x=.5,y=.86]{aa}
\Vertex[x=1,y=0]{10}
\Vertex[x=1.5,y=.86]{bb}
\Vertex[x=2,y=0]{20}
\Vertex[x=2.5,y=-.86]{c}
\Vertex[x=2.5,y=.86]{cc}
\Vertex[x=3,y=0]{30}
\Vertex[x=3.5,y=-.86]{d}
\Vertex[x=4,y=0]{40}
\Vertex[x=4.5,y=-.86]{e}
\Vertex[x=5,y=0]{50}
\Vertex[x=5.5,y=-.86]{f}
\Vertex[x=6,y=0]{60}
\Edges(00,10,a,00,aa,bb,cc,30,40,50,60,f,e,d,c,20,10,aa)
\Edges(10,bb,20,cc)\Edges(20,30,c)
\Edges(30,d,40,e,50,f)
\end{tikzpicture}
\par\end{centering}
\caption{An example of a 2-path.}
\end{figure}
Beineke and Pippert~\cite{Beineke/Pippert 1971} introduced $k$-paths
of $k$-trees, and Proskurowski~\cite{Proskurowski 1984} considered
$k$-paths as graphs. Note that $k$-paths are also known as linear
$k$-trees~\cite{ABELMOSW 2017}. They are closely related to pathwidth
~\cite{PT 1999}; in particular, they are the maximal graphs with proper
pathwidth $k$. They are related to treewidth, zero forcing, and many
related parameters~\cite{BBFHHSVV 2013}, and are extremal interval
graphs~\cite{Eckhoff 1993}. Note that 2-paths are the 2-trees with
the most spanning trees~\cite{RSW 2016} and they characterize the
values of three parameters related to linear algebra~\cite{Hogben/vanderHolst 2007}.
Bickle~\cite{Bickle 2021B} has a survey of $k$-trees, $k$-paths,
and related graph classes.
There is a simple characterization of these graphs.
\begin{theorem}
\textup{\cite{MJP 2006} }Let $G$ be a $k$-tree with order $n>k+1$.
Then $G$ is a $k$-path graph if and only if $G$ has exactly two
$k$-leaves.
\end{theorem}
The number of labeled $k$-paths of order $n$ is $\frac{n!}{2\cdot k!}k^{n-k-2}$.
This was proved by Markenzon et al.~\cite{MVP 2008} using a code
for $k$-paths. Baste et al.~\cite{BNS 2018} have a short proof.
We consider the number of unlabeled $k$-paths of order $n$. Eckhoff
\cite{Eckhoff 1993} studied interval graphs that have maximum size
for a given clique number, and showed that these graphs are equivalent
to interior $k$-caterpillars. Eckhoff (using ideas from Proskurowski
\cite{Proskurowski 1984}) showed that there is a bijection between
interior $k$-caterpillars of order $n$ and $k$-paths of order $n+2$.
Eckhoff used this to prove recurrences for the number of $k$-paths
of order $n$ that depend on smaller values of $k$ and $n$, and
found closed formulas for $2\leq k\leq4$.
One approach to counting $k$-paths is to prove a bijection between
them and strings of numbers (or codes) that satisfy certain conditions.
One approach to this was taken by Pereira et al.~\cite{PGL 2014},
who defined a code based on the unique $k+1$-coloring of a $k$-path.
Thus the code uses integers from $\left\{ 1,2,\ldots,k+1\right\} $.
They define a recurrence by considering dominating vertices and symmetry.
We define a different code for $k$-paths and show that they correspond
to equivalence classes of strings of numbers from $\left\{ 1,2,\ldots,k\right\} $
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. The problem of enumerating such strings was previously
studied by Nester~\cite{Nester 1999} using Polya enumeration. This
produced a method for calculating small values of these sequences,
but did not produce closed formulas for them.
\section{Construction strings}
To count $k$-paths, we need a way to describe their construction
with a string of numbers. A $k$-path with vertices $v_{1}$, \ldots
, $v_{n}$ can be constructed from $K_{k+1}$ by successively adding
$k$-leaves so that $v_{1}$ is always a $k$-leaf, and each $v_{i}$
with $k+1