Discrete Mathematics & Theoretical Computer Science,Vol 8 (2006)

摘要

The Kn-complement of a graphG, denoted by Kn-G, is defined as the graph obtained from the complete graph Kn by removing a set of edges that span G; if G has n vertices, then Kn-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 Kn{m} ± G, where Kn{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 Kn{m}; the graph Knm + G (resp. Knm - G) is obtained from Kn{m} by adding (resp. removing) the edges of G. Moreover, we derive determinant based formulas for graphs that result from Kn{m} by adding and removing edges of multigraphs spanned by sets of edges of the graph Knm. 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.