On the Number of Compositions of K_{m} × P_{n}

Liam Buttitta e-mail: lbuttitta@bytesizedsolutions.com

July 2021

Abstract

In a paper written in 2001, A. Knopfmacher and M. E. Mays introduced the concept of graph compositions. In another paper written in 2004, J. N. Ridley and M. E. 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 On-Line Encyclopedia of Integer Sequences (the OEIS). We also demonstrate some unexpected results that arise from these sequences, and try to explain why they might occur.

Keywords: graph composition, recursive sequence

AMS Classification Numbers: 05

1 Introduction

Knopfmacher and 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 [?] 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 [?] gave a result for the number of compositions of a bipartite graph in terms of exponential