On the number of spanning trees of K n m ± Ggraphs

Abstract

The K n-complement of a graph G, 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 graph G. 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.