Skip to Main content Skip to Navigation
Journal articles

On the number of spanning trees of K_n^m #x00B1 G graphs

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 øverlineG 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 #x00b1 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 #x00b1 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/hal-00961111
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Wednesday, March 19, 2014 - 2:31:22 PM
Last modification on : Wednesday, November 29, 2017 - 10:26:17 AM
Long-term archiving on: : Thursday, June 19, 2014 - 11:59:36 AM

File

dm080114.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00961111, version 1

Collections

Citation

Stavros D. Nikolopoulos, Charis Papadopoulos. On the number of spanning trees of K_n^m #x00B1 G graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2006, 8, pp.235-248. ⟨hal-00961111⟩

Share

Metrics

Record views

198

Files downloads

1984