Eur. Phys. J. Plus (2015) 130: 217
https://doi.org/10.1140/epjp/i2015-15217-y

Regular Article

The deletion-contraction method for counting the number of spanning trees of graphs

¹ Department of Mathematics, Faculty of Science, Taibah University, 41411, Al-Madinah, Saudi Arabia
² 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

Abstract

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.