The Enumeration of Spanning Trees in Dual, Bipartite and Reduced Graphs
Dounia Lotfi, Mohamed El Marraki, Driss Aboutajdine · Journal of Discrete Mathematical Sciences and Cryptography · 2015
In this paper, we deal with the enumeration of spanning trees in planar graphs using some combinatorial structures such as duality, bipartition and reduction. It is well known that the number of spanning trees in a planar graph is equal to the one in its dual. Based on this result, our contribution is to propose a formula that state the relation between the number of spanning trees in a given graph and in its bipartite. Then, similarly we establish a formula for the reduced graph. Finally, we extend the results of the deletion, the contraction and the splitting techniques to investigate the complexity in these combinatorial structures. The main advantage of our proposal is to derive spanning trees recursions in order to over- come the hardiness of computing the complexity of a given planar graph using the existing methods.