Enumeration of spanning trees of middle graphs
| Autor: | Weigen Yan |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
Strongly regular graph Trémaux tree Spanning tree Degree (graph theory) Applied Mathematics 010102 general mathematics Neighbourhood (graph theory) 0102 computer and information sciences 01 natural sciences Combinatorics Computational Mathematics 010201 computation theory & mathematics Graph power Bound graph 0101 mathematics Mathematics Minimum degree spanning tree |
| Zdroj: | Applied Mathematics and Computation. 307:239-243 |
| ISSN: | 0096-3003 |
| Popis: | Let G be a simple graph with n vertices and m edges, and and the maximum degree and minimum degree of G. Suppose G is the graph obtained from G by attaching dG(v) pendent edges to each vertex v of G. Huang and Li (Bull. Aust. Math. Soc. 91(2015), 353367) proved that if G is regular (i.e., =,G=G), then the middle graph of G, denoted by M(G), has 2mn+1m1t(G) spanning trees, where t(G) is the number of spanning trees of G. In this paper, we prove that t(M(G)) can be expressed in terms of the summation of weights of spanning trees of G with some weights on its edges. Particularly, we prove that if G is irregular (i.e., ), then t(M(G))=2mn+1m+k1t(G), where k is the number of vertices of degree one in G. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect