Basic Enumeration of Graph Compositions with a Restricted Number of Components

摘要

A graph composition is a partition of the vertex set of a simple graph such that each member of the partition (called a component) induces a connected subgraph; the composition number of a graph is the number of possible graph compositions. The concept of graph compositions is related to several number theoretic concepts, including partitions of positive integers and the cardinality of the power set of finite sets. This paper examines the composition number of graphs where the total number of components of each composition is restricted.