### On the number of spanning trees of K_{n}^{m} ± G graphs

*Stavros D. Nikolopoulos, Charis Papadopoulos*

#### Abstract

The K

_{n}-complement of a graphG, denoted by K_{n}-G, is defined as the graph obtained from the complete graph K_{n}by removing a set of edges that span G; if G has n vertices, then K_{n}-G coincides with the complement G of the graphG. In this paper we extend the previous notion and derive determinant based formulas for the number of spanning trees of graphs of the form K_{n}^{{m}}± G, where K_{n}^{{m}}is the complete multigraph on n vertices with exactly m edges joining every pair of vertices and G is a multigraph spanned by a set of edges of K_{n}^{{m}}; the graph K_{n}^{m}+ G (resp. K_{n}^{m}- G) is obtained from K_{n}^{{m}}by adding (resp. removing) the edges of G. Moreover, we derive determinant based formulas for graphs that result from K_{n}^{{m}}by adding and removing edges of multigraphs spanned by sets of edges of the graph K_{n}^{m}. We also prove closed formulas for the number of spanning tree of graphs of the form K_{{n}}^{m}± G, where G is (i) a complete multipartite graph, and (ii) a multi-star graph. Our results generalize previous results and extend the family of graphs admitting formulas for the number of their spanning trees.Full Text: PDF PostScript