Lower bounds for the spanning tree numbers of two graph products

Abstract

For any graph $G$ of order $n$, the spanning tree packing number \emph{$STP(G)$}, is the maximum number of edge-disjoint spanning trees contained in $G$. In this paper, we obtain some sharp lower bounds for the spanning tree numbers of Cartesian product graphs and Lexicographic product graphs.

11 pages