\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<i<n$ is a $k$-leaf until $v_{i+1}$ is added. We define
a labeling of the $k$-path so that the two $k$-leaves are unlabeled,
and every other vertex receives a label.

Label the $k$ neighbors of $v_{1}$ with $\left\{ 1,2,\ldots,k\right\} $
(in any way). Each time a $k$-leaf $v_{i+1}$ is added adjacent to
(old) $k$-leaf $v_{i}$, label $v_{i}$ with whatever number in $\left\{ 1,2,\ldots,k\right\} $
is not already a label of a neighbor of $v_{i+1}$. Record each new
label added (after the first $k$) in order.
\begin{definition}
A \textit{construction string} of a $k$-path is the string of $n-k-2$
numbers added after the first $k$ using the algorithm above.
\end{definition}

An example of constructing a 2-path is shown below. The construction
string is recorded below each iteration.

\begin{figure}[h]
\begin{centering}
\begin{tikzpicture}  
\SetVertexSimple[Shape=circle, MinSize=8pt, FillColor=white!50]
\Vertex[x=.5,y=.5]{a}\node at (.5,.2) {$u$};
\Vertex[x=1,y=0]{10}\node at (1,-.3) {$1$};
\Vertex[x=1,y=1]{11}\node at (1,1.3) {$2$};
\Vertex[x=1.5,y=.5]{b}\node at (1.5,.2) {$v$};
\node at (2,.5) {$\rightarrow$};\node at (3.25,-.8) {$2$};
\Vertex[x=2.5,y=.5]{c}\node at (2.5,.2) {$u$};
\Vertex[x=3,y=0]{30}\node at (3,-.3) {$1$};
\Vertex[x=3,y=1]{31}\node at (3,1.3) {$2$};
\Vertex[x=3.5,y=1]{41}\node at (3.5,1.3) {$2$};
\Vertex[x=4,y=.5]{d}
\node at (4.5,.5) {$\rightarrow$};\node at (5.75,-.8) {$21$};
\Vertex[x=5,y=.5]{e}\node at (5,.2) {$u$};
\Vertex[x=5.5,y=0]{50}\node at (5.5,-.3) {$1$};
\Vertex[x=5.5,y=1]{51}\node at (5.5,1.3) {$2$};
\Vertex[x=6,y=0]{60}\node at (6,-.3) {$1$};
\Vertex[x=6,y=1]{61}\node at (6,1.3) {$2$};
\Vertex[x=6.5,y=.5]{f}
\node at (7,.5) {$\rightarrow$};\node at (8.5,-.8) {$211$};
\Vertex[x=7.5,y=.5]{g}\node at (7.5,.2) {$u$};
\Vertex[x=8,y=0]{80}\node at (8,-.3) {$1$};
\Vertex[x=8,y=1]{81}\node at (8,1.3) {$2$};
\Vertex[x=8.5,y=0]{90}\node at (8.5,-.3) {$1$};
\Vertex[x=8.5,y=1]{91}\node at (8.5,1.3) {$2$};
\Vertex[x=9,y=0]{9}\node at (9,-.3) {$1$};
\Vertex[x=9.5,y=.5]{h}
\Edges(10,11,a,10,b,11)\Edges(31,30,c,31,41,d,30,41)
\Edges(51,50,e,51,61,60,50,61,f,60)
\Edges(81,80,g,81,91,90,80,91,9,90)\Edges(9,h,91)
\end{tikzpicture}
\par\end{centering}
\caption{Finding the construction string of a 2-path.}

\end{figure}
\begin{definition}
Let a \textit{$k$-string} be an ordered list of numbers from $\left[k\right]$.
The \textit{reverse-permute} (RP) {\textit relation} treats $k$-strings as
equivalent when they can be made the same by permutation of their
numbers and possible reversal of the string.
\end{definition}

For example, the 2-strings 1112, 2221, 2111, and 1222 are equivalent
under the RP relation. There are six equivalence classes of 2-strings
of length 4, with representatives 1111, 1112, 1121, 1122, 1212, and
1221.
\begin{lemma}
The number of unlabeled $k$-paths of order $n\geq k+3$ equals the
number of equivalence classes of $k$-strings of length $n-k-2$ under
the {\rm RP} relation.
\end{lemma}

\begin{proof}
Consider constructing a $k$-path of order $n$ using the algorithm
described above, producing a construction string of length $n-k-2$.
Since the labeling of the first $k$ labeled vertices is arbitrary,
any permutation of this string can be produced by the $k$-path. It
can also be constructed starting from the other 2-leaf. Constructing
from the other $k$-leaf reverses the string, since each number in
the string corresponds to a copy of $P_{4}+K_{k-1}$ in the $k$-path.
Thus each $k$-path produces an equivalence class of $k$-strings
of length $n-k-2$ under the RP relation.

Alternatively, we can start with a construction string and use it
to construct a $k$-path. Each number specifies a unique way to add
each new vertex, so each construction string produces a single $k$-path.
Thus we have a bijection between $k$-paths of order $n\geq k+3$
and equivalence classes of $k$-strings of length $n-k-2$ under the
RP relation.
\end{proof}

\section{Counting $k$-strings and $k$-paths}

Thus the problem of counting $k$-paths reduces to the problem of
counting equivalence classes of $k$-strings under the RP relation.
These equivalence classes do not all have equal size.
\begin{definition}
A $k$-string has \textit{reversal symmetry} if it can have its numbers
permuted to produce the reverse of the string.
\end{definition}

For example, of the 2-strings of length 4, 1111, 1122, 1212, and 1221
have reversal symmetry and 1112 and 1121 don't. To count $k$-strings,
we must separate them into those with reversal symmetry and those
without.

If a string has reversal symmetry, permuting its numbers to reverse
the string twice must produce the original string. A permutation that
is self-inverse is called an \textit{involution}. An involution must
have cycles of length one or two only. We will need the sequence $s(n)$
of involution numbers. This sequence (\seqnum{A000085} in OEIS, the On-Line
Encyclopedia of Integer Sequences) begins 1, 2, 4, 10, 26, 76, 232,
764, 2620,  \ldots The following formula is easily demonstrated:
\[
s(n)=\sum_{k=0}^{\lfloor n/2\rfloor}\frac{n!}{2^{k}(n-2k)!k!}.
\]

\begin{table}[h]
\begin{centering}
\begin{tabular}{|c|c|}
\hline 
$i$ & $a(i,x)$\tabularnewline
\hline 
1 & $1$\tabularnewline
\hline 
2 & $2\cdot2^{r}-2$\tabularnewline
\hline 
3 & $4\cdot3^{r}-6\cdot2^{r}$\tabularnewline
\hline 
4 & $10\cdot4^{r}-16\cdot3^{r}+8$\tabularnewline
\hline 
5 & $26\cdot5^{r}-50\cdot4^{r}+40\cdot2^{r}-10$\tabularnewline
\hline 
6 & $76\cdot6^{r}-156\cdot5^{r}+160\cdot3^{r}-60\cdot2^{r}-36$\tabularnewline
\hline 
7 & $232\cdot7^{r}-532\cdot6^{r}+700\cdot4^{r}-280\cdot3^{r}-252\cdot2^{r}+112$\tabularnewline
\hline 
\end{tabular}
\par\end{centering}
\caption{Formulas for $a(i,x)$, $r=\lceil \frac{x}{2}\rceil $}
\end{table}

\begin{table}[h]
\begin{centering}
\begin{tabular}{|c|c|}
\hline 
$i$ & $a'(i,x)$\tabularnewline
\hline 
1 & $1$\tabularnewline
\hline 
2 & $2^{r}-2$\tabularnewline
\hline 
3 & $2\cdot3^{r}-3\cdot2^{r}$\tabularnewline
\hline 
4 & $4\cdot4^{r}-8\cdot3^{r}+8$\tabularnewline
\hline 
5 & $10\cdot5^{r}-20\cdot4^{r}+20\cdot2^{r}-10$\tabularnewline
\hline 
6 & $26\cdot6^{r}-60\cdot5^{r}+80\cdot3^{r}-30\cdot2^{r}-36$\tabularnewline
\hline 
7 & $76\cdot7^{r}-182\cdot6^{r}+280\cdot4^{r}-140\cdot3^{r}-126\cdot2^{r}+112$\tabularnewline
\hline 
\end{tabular}
\par\end{centering}
\caption{Formulas for $a'(i,x)$, $r=\lceil \frac{x}{2}\rceil $}
\end{table}
\begin{theorem}
\label{thm:CountkPath}Let $a(1,x)=a'(1,x)=1$,
and 
\[
a(i,x)=s(i)\cdot i^{\lceil \frac{x}{2}\rceil }-\sum_{j=1}^{i-1}\binom{i}{j}a(j,x)s(i-j)
\]
\[
a'(i,x)=s(i-1)\cdot i^{\lceil \frac{x}{2}\rceil }-\sum_{j=1}^{i-1}\binom{i}{j}a'(j,x)s(i-j)
\]
\[
b(i,x)=\sum_{j=1}^{i}(-1)^{i-j}\binom{i}{j}j^{x}.
\]

The number of equivalence classes of $k$-strings of length $x$ under
the RP relation is
\[
\begin{cases}
\sum_{i=1}^{k}\frac{b(i,x)+a(i,x)}{2\cdot i!}, & x\,\text{even;}\\
\sum_{i=1}^{k}\frac{b(i,x)+a'(i,x)}{2\cdot i!}, & x\,\text{odd.}
\end{cases}
\]
\end{theorem}

\begin{proof}
We split the strings into those that have reversal symmetry and those
that do not. Let the number of strings of length $x$ using exactly
$i$ numbers that have reversal symmetry be $a(i,x)$ for
$x$ even, and $a'(i,x)$ for $x$ odd. Certainly $a(1,x)=a'(1,x)=1$.
To find how many strings with reversal symmetry use exactly $i$ numbers,
we find how many use at most $i$ numbers and subtract out those that
use fewer than $i$.

Assume $x$ is even. There are $\lceil \frac{x}{2}\rceil $
number in the first half of the string. There are $i$ choices for
each position, so there are $i^{\lceil \frac{x}{2}\rceil }$
choices for the first half of the string. Since the string has reversal
symmetry, an involution of the first half must produce the second
half, which can happen in $s(i)$ ways. Thus there are
$s(i)\cdot i^{\lceil \frac{x}{2}\rceil }$ strings
with reversal symmetry that use at most $i$ numbers. There are $\binom{i}{j}$
choices of $j$ numbers that appear in a string using exactly $j$
of $i$ numbers. The number of involutions of the remaining $j-i$
numbers is $s(j-i)$, so each string using exactly $j$
of $i$ numbers will appear $\binom{i}{j}a(j,x)s(i-j)$
times in the $s(i)\cdot i^{\lceil \frac{x}{2}\rceil }$
strings. We subtract these out for each $j$ between 1 and $i-1$,
producing the recursive formula 
\[
a(i,x)=s(i)\cdot i^{\lceil \frac{x}{2}\rceil }-\sum_{j=1}^{i-1}\binom{i}{j}a(j,x)s(i-j).
\]

Now let $x$ be odd. As before, to find how many strings with reversal
symmetry use exactly $i$ numbers, we find how many use at most $i$
numbers and subtract out those that use fewer than $i$. A permutation
that reverses the string must fix the middle element, so $s(i-1)$
involutions produce the second half of the string. Thus there are
$s(i-1)\cdot i^{\lceil \frac{x}{2}\rceil }$
strings with reversal symmetry that use at most $i$ numbers. As before,
we have the recursive formula 
\[
a'(i,x)=s(i-1)\cdot i^{\lceil \frac{x}{2}\rceil }-\sum_{j=1}^{i-1}\binom{i}{j}a'(j,x)s(i-j).
\]

Let the total number of strings of length $x$ using exactly $i$
specified numbers of $k$ numbers be $b(i,x)$. Equivalently,
this is the number of onto functions from $\left\{ 1,2,\ldots,k\right\} $
to $\left\{ 1,2,\ldots,i\right\} $. There is a well-known formula for
this, proved using inclusion-exclusion (\cite[p.~561]{Rosen 2011}),
showing $b(i,x)=\sum_{j=1}^{i}(-1)^{i-j}\binom{i}{j}j^{x}.$
Thus the number of strings without reversal symmetry is $b(i,x)-a(i,x)$
or $b(i,x)-a'(i,x)$, depending on parity.

A $k$-string with reversal symmetry using exactly $i$ of $k$ numbers
is part of an equivalence class of $i!$ strings equivalent under
the RP relation. A $k$-string without reversal symmetry using exactly
$i$ of $k$ numbers is part of an equivalence class of $2\cdot i!$
strings equivalent under the RP relation. Thus the number of equivalence
classes of $k$-strings of even length $x$ under the RP relation
is 
\[
\sum_{i=1}^{k}\frac{a(i,x)}{i!}+\sum_{i=1}^{k}\frac{b(i,x)-a(i,x)}{2\cdot i!}=\sum_{i=1}^{k}\frac{b(i,x)+a(i,x)}{2\cdot i!}.
\]
The number of equivalence classes of $k$-strings of odd length $x$
under the RP relation is 
\[
\sum_{i=1}^{k}\frac{a'(i,x)}{i!}+\sum_{i=1}^{k}\frac{b(i,x)-a'(i,x)}{2\cdot i!}=\sum_{i=1}^{k}\frac{b(i,x)+a'(i,x)}{2\cdot i!}.
\]
\end{proof}
\begin{corollary}
The number of unlabeled $k$-paths of order $n\geq k+3$ is 
\[
\begin{cases}
\sum_{i=1}^{k}\frac{b(i,n-k-2)+a(i,n-k-2)}{2\cdot i!}, & n-k\,\text{even;}\\
\sum_{i=1}^{k}\frac{b(i,n-k-2)+a'(i,n-k-2)}{2\cdot i!}, & n-k\,\text{odd.}
\end{cases}
\]
\end{corollary}

For small values of $k$, here are simplified formulas from Theorem
\ref{thm:CountkPath} for the number $N(k,x)$ of $k$-paths
of order $x=n-k-2$.



\begin{align*}
N(2,x) & = \begin{cases}
\frac{1}{4}2^{x}+\frac{1}{2}2^{\left\lceil \frac{x}{2}\right\rceil }, & n\text{ even};\\
\frac{1}{4}2^{x}+\frac{1}{4}2^{\left\lceil \frac{x}{2}\right\rceil }, & n\text{ odd};
\end{cases}=2^{n-6}+2^{\left\lfloor \frac{n-6}{2}\right\rfloor }.\\
N(3,x) & = \begin{cases}
\frac{1}{12}3^{x}+\frac{1}{6}3^{\left\lceil \frac{x}{2}\right\rceil }+\frac{1}{4}, & n\text{ even};\\
\frac{1}{12}3^{x}+\frac{1}{3}3^{\left\lceil \frac{x}{2}\right\rceil }+\frac{1}{4}, & n\text{ odd}.
\end{cases}\\
N(4,x) & = \begin{cases}
\frac{1}{48}4^{x}+\frac{5}{24}4^{\left\lceil \frac{x}{2}\right\rceil }+\frac{1}{8}2^{x}+\frac{1}{3}, & n\text{ even};\\
\frac{1}{48}4^{x}+\frac{1}{12}4^{\left\lceil \frac{x}{2}\right\rceil }+\frac{1}{8}2^{x}+\frac{1}{3}, & n\text{ odd}.
\end{cases}\\
N(5,x) & = \begin{cases}
\frac{5^{x}}{240}+\frac{3^{x}}{24}+\frac{2^{x}}{12}+\frac{5^{\left\lceil \frac{x}{2}\right\rceil }}{24}+\frac{2^{\left\lceil \frac{x}{2}\right\rceil }}{12}+\frac{5}{16}, & n\text{ even};\\
\frac{5^{x}}{240}+\frac{3^{x}}{24}+\frac{2^{x}}{12}+\frac{13\cdot5^{\left\lceil \frac{x}{2}\right\rceil }}{120}+\frac{2^{\left\lceil \frac{x}{2}\right\rceil }}{6}+\frac{5}{16}, & n\text{ odd}.
\end{cases}\\
N(6,x) & = \begin{cases}
\frac{6^{x}}{1440}+\frac{4^{x}}{96}+\frac{3^{x}}{36}+\frac{3\cdot2^{x}}{32}+\frac{19\cdot6^{\left\lceil \frac{x}{2}\right\rceil }}{360}+\frac{3^{\left\lceil \frac{x}{2}\right\rceil }}{9}+\frac{2^{\left\lceil \frac{x}{2}\right\rceil }}{8}+\frac{17}{60}, & n\text{ even};\\
\frac{6^{x}}{1440}+\frac{4^{x}}{96}+\frac{3^{x}}{36}+\frac{3\cdot2^{x}}{32}+\frac{13\cdot6^{\left\lceil \frac{x}{2}\right\rceil }}{720}+\frac{3^{\left\lceil \frac{x}{2}\right\rceil }}{18}+\frac{2^{\left\lceil \frac{x}{2}\right\rceil }}{16}+\frac{17}{60}, & n\text{ odd}.
\end{cases}\\
N(7,x) & = \begin{cases}
\frac{7^{x}}{10080}+\frac{5^{x}}{480}+\frac{4^{x}}{144}+\frac{3^{x}}{32}+\frac{11\cdot2^{x}}{120}+\frac{19\cdot7^{\left\lceil \frac{x}{2}\right\rceil }}{2520}+\frac{4^{\left\lceil \frac{x}{2}\right\rceil }}{36}+\frac{3^{\left\lceil \frac{x}{2}\right\rceil }}{24}+\frac{2^{\left\lceil \frac{x}{2}\right\rceil }}{20}+\frac{85}{288}, & n\text{ even};\\
\frac{7^{x}}{10080}+\frac{5^{x}}{480}+\frac{4^{x}}{144}+\frac{3^{x}}{32}+\frac{11\cdot2^{x}}{120}+\frac{29\cdot7^{\left\lceil \frac{x}{2}\right\rceil }}{1260}+\frac{5\cdot4^{\left\lceil \frac{x}{2}\right\rceil }}{72}+\frac{3^{\left\lceil \frac{x}{2}\right\rceil }}{12}+\frac{2^{\left\lceil \frac{x}{2}\right\rceil }}{10}+\frac{85}{288}, & n\text{ odd}.
\end{cases}
\end{align*}

In general, the dominant term is always $\frac{1}{2\cdot k!}k^{n-k-2}$,
and for $k\geq5$, the next largest term is $\frac{1}{4\cdot(k-2)!}(k-2)^{n-k-2}$.
The following table lists the beginnings of the sequences, and their OEIS numbers.
\begin{table}[h]
\begin{centering}
\begin{tabular}{|c|c|c|}
\hline 
$k$ & Sequence ($n\geq k+3$) & OEIS\tabularnewline
\hline 
\hline 
2 & 1, 2, 3, 6, 10, 20, 36, 72, 136, 272, \ldots & \seqnum{A005418}\tabularnewline
\hline 
3 & 1, 2, 4, 10, 25, 70, 196, 574, 1681, 5002, \ldots & \seqnum{A001998}\tabularnewline
\hline 
4 & 1, 2, 4, 11, 31, 107, 379, 1451, 5611, 22187, \ldots & \seqnum{A056323}\tabularnewline
\hline 
5 & 1, 2, 4, 11, 32, 116, 455, 1993, 9134, 43580, \ldots & \seqnum{A056324}\tabularnewline
\hline 
6 & 1, 2, 4, 11, 32, 117, 467, 2135, 10480, 55091, \ldots & \seqnum{A056325}\tabularnewline
\hline 
7 & 1, 2, 4, 11, 32, 117, 468, 2151, 10722, 58071, \ldots & \seqnum{A345207}\tabularnewline
\hline 
\end{tabular}
\par\end{centering}
\caption{Sequences counting $k$-paths}

\end{table}

All $k$-paths with order $k+3\leq n\leq2k+1$ have diameter 2, and
so have a dominating vertex. If there are $N$ $k$-paths with order
$2k+2$, then there are $N$ $k+t$-paths with order $2k+2+t$, since
they have at least $t$ dominating vertices. Thus the sequences in
the table above approach a limiting sequence of 1, 2, 4, 11, 32, 117,
468, 2152, 10743,  \ldots which is \seqnum{A103293}. 

The formula for the number of 2-paths of order $n\geq5$ simplifies
to $2^{n-6}+2^{\lfloor \frac{n-6}{2}\rfloor }$. Harary
and Schwenk~\cite{Harary/Schwenk 1973} showed that there are $2^{n-4}+2^{\lfloor \frac{n-4}{2}\rfloor }$
caterpillars of order $n\geq3$ using a similar proof technique. Eckhoff
\cite{Eckhoff 1993} and Pereira et al.~\cite{PGL 2014} both showed
that the number of 2-paths of order $n$ equals the number of caterpillars
of order $n-2$ using a natural bijection.


\begin{thebibliography}{10}
\bibitem{ABELMOSW 2017} A. Abiad, B. Brimkov, A. Erey, L. Leshock,
X. Martinez-Rivera, S. O, S. Song, and J. Williford, On the Wiener
index, distance cospectrality and transmission regular graphs, \textit{Discrete
Appl. Math.} \textbf{230} (2017), 1--10.

\bibitem{BBFHHSVV 2013}  F. Barioli, W. Barrett, S. Fallat, H. Hall,
L. Hogben, B. Shader, P. van den Driessche, and H. van der Holst,
Parameters related to tree-width, zero forcing, and maximum nullity
of a graph, \textit{J. Graph Theory} \textbf{72} (2013), 146--177.

\bibitem{BNS 2018}  J. Baste, M. Noy, and I. Valls, On the number
of labeled graphs of bounded treewidth, \textit{European J. Combin.}
\textbf{71} (2018), 12--21.

\bibitem{Beineke/Pippert 1971}  L. W. Beineke and R. E. Pippert,
Properties and characterizations of $k$-trees, \textit{Mathematika}
\textbf{18} (1971), 141--151.

\bibitem{Bickle 2020} A. Bickle, \textit{Fundamentals of Graph Theory},
American Mathematical Society, 2020.

\bibitem{Bickle 2020-1} A. Bickle, $k$-paths of $k$-trees, 
\textit{Congr. Numer.}, to appear.

\bibitem{Bickle 2021} A. Bickle, Maximal $k$-degenerate graphs with
diameter 2, \textit{Int. J. Math. Comb.} \textbf{2} (2021), 67--78.

\bibitem{Bickle 2021B} A. Bickle, A survey of maximal $k$-degenerate
graphs and $k$-trees, 2021. Submitted.

\bibitem{Eckhoff 1993}  J. Eckhoff, Extremal interval graphs, \textit{J.
Graph Theory} \textbf{17} (1993), 117--127.

\bibitem{Harary/Schwenk 1973} F. Harary and A. Schwenk, The number
of caterpillars, \textit{Discrete Math.} \textbf{6} (1973), 359--365.

\bibitem{Hogben/vanderHolst 2007}  L. Hogben and H. van der Holst,
Forbidden minors for the class of graphs $g$ with $\xi(g)\leq2$,
\textit{Linear Algebra Appl.} \textbf{423} (2007), 42--52.

\bibitem{MJP 2006} L. Markenzon, C. M. Justel, and N. Paciornik,
Subclasses of $k$-trees: characterization and recognition, \textit{Discrete
Appl. Math.} \textbf{154} (2006), 818--825.

\bibitem{MVP 2008}   L. Markenzon, O. Vernet, and P. R. da Costa
Pereira, A clique-difference encoding scheme for labelled $k$-path
graphs, \textit{Discrete Appl. Math.} \textbf{156} (2008), 3216--3222.

\bibitem{Nester 1999} M. R. Nester, Mathematical investigations of
some plant interaction designs. PhD Thesis, University of Queensland,
Brisbane, Australia (1999).

\bibitem{PGL 2014}  P. Pereira, A. Garcia, and L. Markenzon, Generating
and counting unlabeled $k$-path graphs, \textit{Discrete Appl. Math.},
\textbf{164} (2014), 297--303.

\bibitem{Proskurowski 1984}  A. Proskurowski, Separating subgraphs
in $k$-trees: cables and caterpillars, \textit{Discrete Math.} \textbf{49}
(1984), 275--285.

\bibitem{PT 1999} A. Proskurowski and J. Telle, Classes of graphs
with restricted interval models, \textit{Discrete Math. Theoret. Comput.
Sci.} \textbf{3} (1999), 167--176.

\bibitem{RSW 2016}  P. Renjith, N. Sadagopan, and D. B. West, Spanning
trees in 2-trees, Arxiv preprint, 2016.  Available
at \url{https://arxiv.org/abs/1607.05817}.

\bibitem{Rosen 2011} K. Rosen, \textit{Discrete Mathematics and Its
Applications}, 7th Edition, McGraw Hill, 2011.
\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2020 {\it Mathematics Subject Classification}:
Primary 05C30.

\noindent \emph{Keywords: } 
$k$-path, $k$-tree, recurrence, involution, caterpillar.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000085},
\seqnum{A001998},
\seqnum{A005418},
\seqnum{A056323},
\seqnum{A056324},
\seqnum{A056325},
\seqnum{A103293}, and
\seqnum{A345207}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received June 11 2021;
revised versions received June 17 2021; March 28 2022; April 2 2022.
Published in {\it Journal of Integer Sequences}, June 21 2022.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                


