A Variant of the Teufl‐Wagner Formula and Applications
Danyi Li, Weigen Yan
Abstract
ABSTRACT Let and be two electrically equivalent edge‐weighted connected graphs with respect to (hence ). Let be a forest in . Denote by the sum of weights of spanning trees of and by the sum of weights of spanning trees each of which containing all edges in , where the weight of a subgraph of is the product of weights of edges in . Suppose that is the edge‐weighted graph obtained from by identifying all vertices in of into a new vertex for . In this paper, we obtain a variant of the Teufl‐Wagner formula (Linear Alg Appl, 432 (2010), 441–457) and prove that . As applications, we enumerate spanning trees of some graphs containing all edges in a given forest and give a simple proof of Moon's formula (Mathematika, 11 (1964), 95–98) and the Dong‐Ge formula (J Graph Theory, 101 (2022), 79–94). In particular, we count spanning trees with a perfect matching in some graphs.