Weighted complexities of graph products and bundles

Abstract

The complexity kappa(G) of a graph G is the number of spanning trees in G. In spite of its importance, most known methods for computing kappa(G) commonly have computational difficulties since they require to compute determinants or eigenvalues of matrices of the size of the order of a graph. In particular, they are not feasible for large graphs. However, many of them can be represented by some graph operations. A graph bundle is a notion containing a cartesian product of graphs and a (regular or irregular) graph covering. For a regular graph covering, H. Mizuno and I. Sato [Zeta functions for images of graph coverings by some operations, Interdiscip. Inform. Sci. 7 (2001) 53-60] computed its complexity. We extend their work to a graph bundle by deriving a factorized formula for the complexity: If a graph bundle has a regular fibre, its complexity can be factorized into the complexity of the base graph and determinants of smaller-size matrices. For the complexities of the cartesian products of graphs, several computing formulae are already known. However, they also used somewhat complicated calculations of determinants, eigenvalues or trigonometric equations. We reduce such complication for the known cases of the ladder, the Mobius ladder and the prism, by simply deriving the factorized formulae for their complexities. New concrete formulae for the complexities of the product P-n x K-m of the path P-n and the complete graph K-m and those of K-m-bundles over the cycle C-n are also derived as generalizations of the prism and the Mobius ladder. (c) 2005 Elsevier Ltd. All fights reserved.