\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage{enumitem}

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

\begin{document}

\begin{center}
\includegraphics[width=4in]{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 
On the Number of Compositions of $K_m \times P_n$
}
\vskip 1cm
\large
Liam Buttitta \\
\href{mailto:lbuttitta@bytesizedsolutions.com}{\tt lbuttitta@bytesizedsolutions.com} 
\end{center}

\vskip .2 in

\begin{abstract}
In a paper written in 2001, Knopfmacher and Mays introduced the concept of graph compositions.
In another paper written in 2004, Ridley and Mays proved a theorem on the number of compositions of the Cartesian product of the path graph with another graph.
We build on this theorem to create an algorithm that calculates the closed-form solutions for the sequences given by the numbers of compositions of the Cartesian product of the path graph with complete graphs, and we apply this algorithm to produce two new sequences in the 
{\it On-Line Encyclopedia of Integer Sequences}.
We also demonstrate some unexpected results that arise from these sequences, and try to explain why they might occur.
\end{abstract}

\section{Introduction}
Knopfmacher and Mays \cite{knopfmacher+mays} defined a composition of a graph $G$ as a partition of $V(G)$ into vertex subsets whose induced subgraphs are connected, although it can also refer to the union of those induced subgraphs.
Ridley and Mays \cite{ridley+mays} later proved a theorem which, given two graphs $G$ and $H$ as well as the numbers of compositions of $G$ and $H$, gives the number of compositions of the union of those two graphs.

Besides Knopfmacher, Ridley, and Mays, there have been several other papers on the theory of compositions.
To name a few, Huq \cite{huq} gave a result for the number of compositions of a bipartite graph in terms of exponential functions; Bajguz \cite{bajguz} gave a result for the number of compositions of trees of connected graphs; and recently, {\'A}rend{\'a}s and others \cite{arendas} found a polynomial which gives the number of compositions of complements of certain graphs with respect to the complete graph.
Nevertheless, surprisingly little work has been done in this field.

We will use the theorem proved by Ridley and Mays, as well as its corollary concerning Cartesian products of graphs, to develop an algorithm written in pseudocode.
This algorithm takes a positive integer $m$ and yields a closed-form solution for the sequence given by the composition of the $m$-complete graph with path graphs of increasing length.
More formally, it returns a closed-form expression for the sequence $(C(K_m \times P_n))_{n=1}^{\infty}$.

We will then apply this algorithm to $K_2$, $K_3$, and $K_4$ to calculate the composition counts of $K_2 \times P_n$, $K_3 \times P_n$, and $K_4 \times P_n$ (illustrated below).
We will also examine those results and investigate some of the patterns they display.
Finally, we suggest possible avenues for further research.
\subsection{Notation}
We make use of the following notation.
\begin{itemize}
    \item
          For a graph $G$, we let $V(G)$ denote the vertices of $G$, and we let $E(G)$ denote the edges of $G$.
    \item
          For a graph $G$, we let $C(G)$ denote the number of compositions of $G$.

          \begin{minipage}{\linewidth}
              For example, $C(C_4) = 12$.
              \begin{figure}[H]
                  \centering
                  \includegraphics[scale=0.5]{C_4-compositions.png}
                  \caption{the compositions of $C_4$}
                  \label{fig:c_4-compositions}
              \end{figure}
              \vspace{0pt}
          \end{minipage}
    \item
          For graphs $G$ and $H$, we let $G \times H$ denote the Cartesian graph product of $G$ and $H$.
          In other words, the vertices of $G \times H$ are $V(G) \times V(H)$, and for any combination of $g_1, g_2 \in V(G)$ and $h_1, h_2 \in V(H)$, $(g_1, h_1)$ and $(g_2, h_2)$ are adjacent in $G \times H$ iff either $g_1 = g_2$ and $h_1$ and $h_2$ are adjacent in $H$, or $h_1 = h_2$ and $g_1$ and $g_2$ are adjacent in $G$.
              For example, below are illustrated the Cartesian products of some complete graphs with $P_4$.
              \begin{figure}[H]
                  \centering
                  \includegraphics[scale=0.5]{K_2xP_4.png}
                  \caption{$K_2 \times P_4$}
                  \label{fig:k_2xp_4}
              \end{figure}

              \begin{figure}[H]
                  \centering
                  \includegraphics[scale=0.5]{K_3xP_4.png}
                  \caption{$K_3 \times P_4$}
                  \label{fig:k_3xp_4}
              \end{figure}
              \begin{figure}[H]
                  \centering
                  \includegraphics[scale=0.5]{K_4xP_4.png}
                  \caption{$K_4 \times P_4$}
                  \label{fig:k_4xp_4}
              \end{figure}

    \item
          For graphs $G$ and $H$, we let $G \cup H$ denote the graph union of $G$ and $H$, and we let $G \cap H$ denote the graph intersection of $G$ and $H$.
          In other words, the vertices of $G \cup H$ are $V(G) \cup V(H)$, and the edges of $G \cup H$ are $E(G) \cup E(H)$.
          Likewise, we let $G \cap H$ denote the graph intersection of $G$ and $H$, and so the vertices of $G \cap H$ are $V(G) \cap V(H)$, and the edges of $G \cap H$ are $E(G) \cap E(H)$.
\end{itemize}
\section{Algorithm}
\subsection{Definitions}
We make use of the following results by Ridley and Mays \cite{ridley+mays}.
\begin{definition}[Type of a vertex pair]
    A vertex pair $(a, b) \in V(H)^2$ on a composition $H$ of a graph $G$ is defined as being \textit{type 0} if no edges must be added from $G$ to $H$ in order for $a$ and $b$ to be connected.
    Similarly, $(a, b)$ is defined as being \textit{type 1} if one edge must be added, or \textit{type 2} if two or more edges must be added.
\end{definition}
\begin{theorem}
    Let $A$ and $B$ be graphs.
    Let $C_0(A), \ldots, C_{k-1}(A)$ denote the numbers of compositions of $A$ in the $k$ cases determined by the possible types of pairs of vertices in $A \cap B$, and for each case $r = 0, 1, \ldots, k - 1$, let $M_r$ denote the number of valid compositions of $G$ obtained by considering all compositions of $B$.
    Then $C(G) = M_0C_0(A) + \cdots + M_{k-1}C_{k-1}(A)$.
\end{theorem}
\begin{corollary}
    If $G_n = A \times P_n$ for each $n = 1, 2, 3, \ldots$, then $C(G_n) = \mathbf{z} \mathbf{M}^{n-1} \mathbf{w}_1$, where $\mathbf{z}$ is the $1 \times k$ row vector $(1 \cdots 1)$, $\mathbf{w}_1$ is a $k \times 1$ column vector, and $\mathbf{M}$ is a $k \times k$ matrix.
\end{corollary}
For convenience, we will also use the following definition in the description of the algorithm.
\begin{definition}[Case of a vertex set]
    For a vertex set $V$ and a composition $H$ on a graph $G$, define the \textit{case} of $V$ on $H$ as the vector whose elements are given by taking the types of each pair of vertices in $V$.
\end{definition}
\subsection{Statement}
The following algorithm takes a positive integer $m$ and yields the values of $\mathbf{w}_1$ and $\mathbf{M}$ which fulfill the conditions of Corollary 2.1.1 when $A = K_m$.
\begin{enumerate}[labelindent=0.8in,leftmargin=*]
    \item[Step 1.1.]
          Let $V(K_m)^2$ denote the arbitrarily ordered set of pairs of vertices of $K_m$.
    \item[Step 1.2.]
          Let $S'$ be the ones vector of length $m^2$.
          Let $S$ be the arbitrarily ordered set of nonnegative integer vectors whose elements are not greater than the corresponding elements of $S'$.
          (For example, if $S'$ were $\mathbf{1}_2$, then
	  $S$ would be \\ $\{(0, 0), (0, 1), (1, 0), (1, 1))\}$.)
    \item[Step 1.3.]
          Remove each element $s$ of $S$ where, for some element $(v_1, v_3)$ of $V(A)^2$, there exists some element $v_2$ of $V(A)$ where the sum of the elements in $s$ corresponding to $(v_1, v_2)$ and $(v_2, v_3)$ is less than the element in $s$ corresponding to $(v_1, v_3)$.
    \item[Step 2.1.]
          Let $B$ be $K_m \times P_2$.
    \item[Step 2.2.]
          Let $B'$ be one of the two subgraphs of $B$ which are congruent to $K_m$.
          Remove the edges of $B'$ from $B$.
    \item[Step 2.3.]
          Let $V(K_m)_1^2$ denote the set of pairs of vertices of the subgraph of $B$ congruent to $K_m$ whose edges were not removed from $B$.
          Let $V(K_m)_2^2$ denote the set of pairs of vertices of $B'$.
    \item[Step 2.4.]
          For each element $(v_1, v_2)$ of $V(K_m)_2^2$, let $n$ be the element of $S$ corresponding to $(v_1, v_2)$, then construct an $n$-path graph with starting point $v_1$ and ending point $v_2$.
          Let $C$ be the graph union of the graphs so constructed.
    \item[Step 3.1.]
          For each $i \in [1, |S|]$, let $(\mathbf{w}_1)_i$ be the number of compositions of $K_m$ on which $V(K_m)$ is case $i$.
    \item[Step 3.2.]
          For each $j \in [1, |S|]$, let $C'$ be some composition of $C$ on which the case of $V(K_m)_2^2$ is $K_j$.
          Then, for each $i \in [1, |S|]$, let $\mathbf{M}_{ij}$ be the number of compositions of $B \cup C'$ on which the case of $V(K_m)_1^2$ is $S_i$ and the case of $V(K_m)_2^2$ is $S_j$.
\end{enumerate}
\begin{example}
    If we apply this algorithm step-by-step to $K_2$, the results at each step are as follows.
    (For convenience, let $\{a_1, a_2\}$ denote the vertices of $K_2$.)
    \begin{itemize}
        \item
              At step 1.1, $V(A)^2$ is set to $\{(a_1, a_2)\}$.
        \item
              At step 1.2, $S'$ is set to $(1)$, and $S$ is set to $\{(0), (1)\}$.
        \item
              At step 1.3, no elements are removed from $S$, so the final value of $S$ is $\{(0), (1)\}$.
        \item
              At step 2.1, $B$ is set to $K_2 \times P_2$.
        \item
              At step 2.2, $B'$ is set to one of the subgraphs of $B$ which are congruent to $A$, and then the edges of $B'$ are removed from $B$.
              (Note that $B$ is now congruent to $P_4$.)
        \item
              At step 2.3, $V(A)_1^2$ and $V(A)_2^2$ are both set to sets of pairs of vertices.
        \item
              At step 2.4, the edge that was removed in step 2.2 is added back.

              (For convenience, let $\{(a_{11}, a_{12})\}$ denote $V(A)_1^2$, and let $\{(a_{21}, a_{22})\}$ denote $V(A)_2^2$.)
        \item
              At step 3.1, $(\mathbf{w}_1)_1$ is set to 1, since there is 1 composition of $K_2$ on which $(a_1, a_2)$ is of type 0.
              Similarly, $(\mathbf{w}_1)_2$ is also set to 1, so the final value of $\mathbf{w}_1$ is $(1, 1)$.
        \item
              At step 3.2, when $j = 1$, $C'$ is set to a graph with one edge connecting $a_{11}$ and $a_{12}$.
              When $i = 1$, $\mathbf{M}_{11}$ is set to 2, since there are 2 compositions of $B \cup C'$ (illustrated below in red) on which $(a_{11}, a_{12})$ and $(a_{21}, a_{22})$ are both of type 0.
              Similarly, when $i = 2$, $\mathbf{M}_{12}$ is set to 3, since there are 3 valid compositions of $B \cup C'$ (illusrated below in blue).

              \begin{figure}[H]
                  \centering
                  \includegraphics[scale=0.5]{j=1-BC-compositions.png}
                  \caption{the compositions of $B \cup C'$ when $j = 1$}
                  \label{fig:j=1-bc-compositions}
              \end{figure}
              When $j = 2$, $C'$ is set to a graph with vertices $\{a_{11}, a_{12}\}$ and no edges.
              When $i = 1$, $\mathbf{M}_{21}$ is set to 3, since there are 3 valid compositions of $B \cup C'$ (illustrated below in yellow).
              Similarly, when $i = 2$, $\mathbf{M}_{22}$ is set to 4, since there are 4 valid compositions of $B \cup C'$ (illustrated below in green).
              (One composition of $B \cup C'$ is not counted towards either entry, since the type of $(a_{11}, a_{12})$ on it is 0.)

              \begin{figure}[H]
                  \centering
                  \includegraphics[scale=0.5]{j=2-BC-compositions.png}
                  \caption{the compositions of $B \cup C'$ when $j = 2$}
                  \label{fig:j=2-bc-compositions}
              \end{figure}
    \end{itemize}
    The final value of $\mathbf{M}$ is $\begin{pmatrix} 2 & 3 \\ 3 & 4 \end{pmatrix}$.
\end{example}
\subsection{Remarks}
Rather than enumerating over each composition of $K_m \times P_n$ and checking if there exists some composition of $A \times P_{n-1}$ from which it could be built, we need merely construct one composition of $C$ for each possible case of $V(A)_2^2$, then check the compositions of $B \cup C'$.
Introducing this substitution makes the algorithm much faster, and its validity is a trivial corollary of the following theorem.
\begin{theorem}
    Let $G$ and $H$ be two graphs and let $G'_1$, $G'_2$ be two compositions of $G$.
    Then if $V(G \cap H)$ is of the same case on $G'_1$ as on $G'_2$, then $V(G \cap H)$ is of the same case on $G'_1 \cup H$ as on $G'_2 \cup H$.
\end{theorem}
\begin{proof}
    First, we define the set of \textit{missing edges} in a path $P$ on a composition $H$ of a graph $G$ as the set of edges in $G \setminus H$.

    For any vertex pair $(a, b) \in V(G \cap H)^2$, let $P_1$ be the path in $G'_1 \cup H$ with endpoints $a$ and $b$ with the least missing edges, and let $P_2$ be a path constructed in $G'_2$ in the same way.

    Suppose that $P_1$ has more edges that are not in $G_1$ than $P_2$ does that are not in $G_2$, or vice versa.
    Then, since the only difference between $G'_1 \cup H$ and $G'_2 \cup H$ is in $G \setminus H$, there must exist at least one pair of subpaths in $G \setminus H$ with the same endpoints, but different numbers of missing edges.

    Let $P'_1$ be the subpath of $P_1$ in $G \setminus H$ with the least missing edges, and let $P'_2$ be the subpath of $P_2$ in $G \setminus H$, such that $P_1$ and $P_2$ have the same endpoints $(c, d) \in V(G \cap H)^2$.
    But since $V(G \cap H)$ is of the same case on $G'_1$ as on $G'_2$, the number of missing edges in the path in $G'_1$ with endpoints $(c, d)$ with the least missing edges, and the number of missing edges in the path constructed in $G'_2$ in the same way, must be equal.
    This is a contradiction.
    Therefore, $P_1$ and $P_2$ must have the same number of missing edges, so for all $(a, b) \in V(G \cap H)^2$, $(a, b)$ must be of the same type on $G'_1$ as on $G'_2$.
\end{proof}
\section{Results}
\subsection{Values}
\begin{minipage}{\textwidth}
    The results of applying the algorithm to $K_m$ for $m \in [1, 4]$, as well as the corresponding entries in the On-Line Encyclopedia of Integer Sequences (OEIS), are as follows.
    \begin{table}[H]
        \centering
        \begin{tabular}{c|c c c c}
            $m$ & $\mathbf{w}_1$    & $\mathbf{M}$ & $(C(K_m \times P_n))_{i=1}$            & OEIS \#          \\ \hline
            1   & $(1)$             & $(2)$        & $1, 2, 4, 8, 16, \ldots$               & \seqnum{A000079} \\
            2   & $(1, 1)$          & see below    & $2, 12, 74, 456, 2810, 17316, \ldots$  & \seqnum{A078469} \\
            3   & $\mathbf{1}_5$    & see below    & $5, 114, 2712, 64518, 1534872, \ldots$ & \seqnum{A346273} \\
            4   & $\mathbf{1}_{15}$ & see below    & $15, 1548, 168386, 18328142, \ldots$   & \seqnum{A344638}
        \end{tabular}
        \caption{the results of the algorithm, applied to $K_m$}
        \label{tab:k_m-results}
    \end{table}
    \vspace{0pt}
\end{minipage}
where, for $m = 2$,
\begin{equation}
    \mathbf{M} =
    \begin{pmatrix}
        2 & 3 \\
        3 & 4
    \end{pmatrix};
\end{equation}
for $m = 3$,
\begin{equation}
    \mathbf{M} =
    \begin{pmatrix}
        8 & 6 & 6 & 6 & 4 \\
        6 & 4 & 5 & 5 & 3 \\
        6 & 5 & 4 & 5 & 3 \\
        6 & 5 & 5 & 4 & 3 \\
        4 & 3 & 3 & 3 & 2
    \end{pmatrix};
\end{equation}
and for $m = 4$,
\begin{equation}
    \setcounter{MaxMatrixCols}{15}
    \mathbf{M} =
    \begin{pmatrix}
        16 & 12 & 12 & 12 & 12 & 12 & 12 & 9 & 9 & 9 & 8 & 8 & 8 & 8 & 5 \\
        12 & 8  & 10 & 10 & 9  & 10 & 10 & 6 & 8 & 8 & 6 & 6 & 7 & 7 & 4 \\
        12 & 10 & 8  & 9  & 10 & 10 & 10 & 8 & 6 & 8 & 6 & 7 & 6 & 7 & 4 \\
        12 & 10 & 9  & 8  & 10 & 10 & 10 & 8 & 6 & 8 & 7 & 6 & 7 & 6 & 4 \\
        12 & 9  & 10 & 10 & 8  & 10 & 10 & 6 & 8 & 8 & 7 & 7 & 6 & 6 & 4 \\
        12 & 10 & 10 & 10 & 10 & 8  & 9  & 8 & 8 & 6 & 7 & 6 & 6 & 7 & 4 \\
        12 & 10 & 10 & 10 & 10 & 9  & 8  & 8 & 8 & 6 & 6 & 7 & 7 & 6 & 4 \\
        9  & 6  & 8  & 8  & 6  & 8  & 8  & 4 & 7 & 7 & 5 & 5 & 5 & 5 & 3 \\
        9  & 8  & 6  & 6  & 8  & 8  & 8  & 7 & 4 & 7 & 5 & 5 & 5 & 5 & 3 \\
        9  & 8  & 8  & 8  & 8  & 6  & 6  & 7 & 7 & 4 & 5 & 5 & 5 & 5 & 3 \\
        8  & 6  & 6  & 7  & 7  & 7  & 6  & 5 & 5 & 5 & 4 & 5 & 5 & 5 & 3 \\
        8  & 6  & 7  & 6  & 7  & 6  & 7  & 5 & 5 & 5 & 5 & 4 & 5 & 5 & 3 \\
        8  & 7  & 6  & 7  & 6  & 6  & 7  & 5 & 5 & 5 & 5 & 5 & 4 & 5 & 3 \\
        8  & 7  & 7  & 6  & 6  & 7  & 6  & 5 & 5 & 5 & 5 & 5 & 5 & 4 & 3 \\
        5  & 4  & 4  & 4  & 4  & 4  & 4  & 3 & 3 & 3 & 3 & 3 & 3 & 3 & 2
    \end{pmatrix}.
\end{equation}
\subsection{Properties}
The matrices associated with $K_m$ have in common several unusual properties.
For example, unlike other graphs' matrices, the matrices associated with $K_m$ are symmetric.

This is because any two vertices on $K_m$ are adjacent, so there exists a trivial bijective map between a possible case of $V(A)_{n-1}$ and a composition of $K$.
This means that it is possible, for all $i \in [1, k]$, to choose a composition of $G_{n-1}$ which is congruent with a composition of $K_m$, which in turn means that it is possible for all compositions in all $G'$ to be congruent with a composition of $K_m \times P_2$.
Finally, since there exists a bijective map between a composition in some $G'$ on which $V(A)_{n-1}$ is of case $i$ and $V(A)_n$ is of case $j$, and one on which $V(A)_{n-1}$ is of case $j$ and $V(A)_n$ is of case $i$, it follows that for $i, j \in [1, n]$, $\mathbf{M}_{ij} = \mathbf{M}_{ji}$.

The matrices associated with $K_m$ also yield unusually simple recurrence relations; for example,
\begin{equation}
    C(K_2 \times P_{n + 2}) = 6C(K_2 \times P_{n + 1}) + C(K_2 \times P_n),
\end{equation}
\begin{equation}
    C(K_3 \times P_{n + 2}) = 24C(K_3 \times P_{n + 1}) + 5C(K_3 \times P_n),
\end{equation}
and
\begin{equation}
    \begin{split}
        C(K_4 \times P_{n + 5}) & = 112C(K_4 \times P_{n + 4}) - 346C(K_4 \times P_{n + 3}) \\
        & + 306C(K_4 \times P_{n + 2}) - 57C(K_4 \times P_{n + 1}) \\
        & + 2C(K_4 \times P_n).
    \end{split}
\end{equation}

As Ridley and Mays's results predict, the dimensions of these matrices are given by the Bell numbers (sequence \seqnum{A000110} in the OEIS).
Nevertheless, the order of the recurrence relations which describe them are unusually low.
Exactly why this happens is not apparent, although it is likely related to the complete graph's simplicity of structure.
\section{Conclusion}
We used the results of Ridley and Mays to develop an algorithm in pseudocode.
This algorithm takes a graph and yields the closed-form solution for the sequence given by the composition of that graph with path graphs of increasing length.

We applied this algorithm to $K_2$, $K_3$, and $K_4$ to calculate the composition counts of $K_2 \times P_n$, $K_3 \times P_n$, and $K_4 \times P_n$.
We also examined those results and investigated some of the patterns they display.

Some interesting areas for further research include why complete graphs yield such simple recurrence relations; how this algorithm could be generalized beyond path graphs; and whether there might be an even simpler formulation equivalent to the results of this algorithm.

Credit to Prof.\ Greg Dresden, who helped me greatly throughout the process of writing this paper.


\begin{thebibliography}{9}

\bibitem{arendas}
P.~{\'A}rend{\'a}s, Ferenc Bencs, Zolt{\'a}n Bl{\'a}zsik, and Csaba Szab{\'o},
Compositions of complements of graphs, {\em
  Integers} {\bf 16} (2016), Paper A29.

\bibitem{bajguz}
W.~Bajguz, Graph and union of graphs compositions, preprint, 2006.
\newblock Available at \url{https://arxiv.org/abs/math/0601755}.

\bibitem{huq}
A.~Huq, Compositions of graphs revisited, {\em Electron. J. Combin.} {\bf 14}
 (1) (2007), Paper N15.

\bibitem{knopfmacher+mays}
A.~Knopfmacher and M.~E. Mays, Graph compositions {I}: Basic enumeration, {\em
  Integers} {\bf 1} (4) (2001), Paper A4.

\bibitem{ridley+mays}
J.~N. Ridley and M.~E. Mays, Compositions of unions of graphs, {\em Fibonacci
  Quart.} {\bf 43} (2004), 222--230.

\end{thebibliography}

\bigskip
\hrule
\bigskip

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

\noindent \emph{Keywords: } graph composition, recursive sequence.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000079},
\seqnum{A000110},
\seqnum{A078469},
\seqnum{A344638}, and
\seqnum{A346273}.)


\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received October 21 2021; 
revised versions received January 2 2022; February 1 2022.
Published in {\it Journal of Integer Sequences}, March 27 2022.

\bigskip
\hrule
\bigskip

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

\end{document}
