Geodesic
On the number of spanning trees of K_n^m #x00B1 G graphs
Discrete mathematics & theoretical computer science, Tome 8 (2006).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2006_8_a5,
     author = {Nikolopoulos, Stavros D. and Papadopoulos, Charis},
     title = {On the number of spanning trees of {K_n^m} {#x00B1} {G} graphs},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {8},
     year = {2006},
     doi = {10.46298/dmtcs.364},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.364/}
}
TY  - JOUR
AU  - Nikolopoulos, Stavros D.
AU  - Papadopoulos, Charis
TI  - On the number of spanning trees of K_n^m #x00B1 G graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2006
VL  - 8
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.364/
DO  - 10.46298/dmtcs.364
LA  - en
ID  - DMTCS_2006_8_a5
ER  - 
%0 Journal Article
%A Nikolopoulos, Stavros D.
%A Papadopoulos, Charis
%T On the number of spanning trees of K_n^m #x00B1 G graphs
%J Discrete mathematics & theoretical computer science
%D 2006
%V 8
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.364/
%R 10.46298/dmtcs.364
%G en
%F DMTCS_2006_8_a5
Nikolopoulos, Stavros D.; Papadopoulos, Charis. On the number of spanning trees of K_n^m #x00B1 G graphs. Discrete mathematics & theoretical computer science, Tome 8 (2006). doi : 10.46298/dmtcs.364. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.364/

Cité par Sources :