https://doi.org/10.1140/epjp/i2015-15217-y
Regular Article
The deletion-contraction method for counting the number of spanning trees of graphs
1
Department of Mathematics, Faculty of Science, Taibah University, 41411, Al-Madinah, Saudi Arabia
2
Department of Mathematics, Faculty of Science, Menoufia University, 32511, Shebin El Kom, Egypt
* e-mail: salamadaoud@gmail.com
Received:
15
June
2015
Revised:
18
September
2015
Accepted:
21
September
2015
Published online:
28
October
2015
In this paper we will be concerned with some combinatorial methods that enable us to determine the number of spanning trees of a graph. Although these methods apply only to rather restricted classes of graphs, sometimes strikingly simple calculations reveal the number of spanning trees of seemingly complex graphs, we presented techniques to derive spanning trees recursions in graphs. Then, we gave the generalization for these techniques. Finally, making use of our results, we investigated the complexity of some new graphs.
© Società Italiana di Fisica and Springer-Verlag Berlin Heidelberg, 2015
