On the Number of Specific Spanning Subgraphs of the Graphs $G\times F$

Abstract

This paper investigates the number of spanning subgraphs of the product of an arbitrary graph $G$ with the path graphs $P_n$ on $n$ vertices that meet certain properties: connectivity, acyclicity, Hamiltonicity, and restrictions on degree. A general method is presented for constructing a recurrence equation $R(n)$ for the graphs $G\times P_n$, giving the number of spanning subgraphs that satisfy a given combination of the properties. The primary result is that all constructed recurrence equations are homogeneous linear recurrence equations with integer coefficients. A second result is that the property “having a spanning tree with degree restricted to $1$ and $3$” is a comparatively strong property, just like the property “having a Hamilton cycle”, which has been studied extensively in literature.