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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2006, 8, pp.235-248
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00961111
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 19 mars 2014 - 14:31:22
Dernière modification le : mercredi 29 novembre 2017 - 10:26:17
Document(s) archivé(s) le : jeudi 19 juin 2014 - 11:59:36

Fichier

dm080114.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

91

Téléchargements de fichiers

783