Enumerating spanning trees of graphs with an involution

As the extension of the previous work by Ciucu and the present authors [M. Ciucu, W.G. Yan, F.J. Zhang, The number of spanning trees of plane graphs with reflective symmetry, J. Combin. Theory Ser. A 112 (2005) 105-116], this paper considers the problem of enumeration of spanning trees of weighted graphs with an involution which allows fixed points. We show that if G is a weighted graph with an involution, then the sum of weights of spanning trees of G can be expressed in terms of the product of the sums of weights of spanning trees of two weighted graphs with a smaller size determined by the involution of G. As applications, we enumerate spanning trees of the almost-complete bipartite graph, the almost-complete graph, the Möbius ladder, and the almost-join of two copies of a graph.     

Connected graphs with a minimal number of spanning trees

The problem studied is the following: Find a simple connected graph G with given numbers of vertices and edges which minimizes the number t_μ(G), the number of spanning trees of the multigraph obtained from G by adding μ parallel edges between every pair of distinct vertices. If G is nearly complete (the number of edges qis ≥(₂^P)?p+2 where p is the number of vertices), then the solution to the minimization problem is unique (up to isomorphism) and the same for all values of μ. The present paper investigates the case whereq<(₂^P)?p+2. In this case the solution is not always unique and there does not always exist a common solution for all values of μ. A (small) class of graphs is given such that for any μ there exists a solution to the problem which is contained in this class. For μ = 0 there is only one graph in the class which solves the problem. This graph is described and the minimum value of t₀(G) is found. In order to derive these results a representation theorem is proved for the cofactors of a special class of matrices which contains the tree matrices associated with graphs.     

Edge disjoint spanning trees in random graphs

We show that almost everyG _m-out containsm edge disjoint spanning trees.     

On the spanning trees of weighted graphs

Given a weighted graph, letW ₁,W ₂,W ₃,... denote the increasing sequence of all possible distinct spanning tree weights. Settling a conjecture due to Kano, we prove that every spanning tree of weightW ₁ is at mostk–1 edge swaps away from some spanning tree of weightW _k . Three other conjectures posed by Kano are proven for two special classes of graphs. Finally, we consider the algorithmic complexity of generating a spanning tree of weightW _k .This work was supported in part by a grant from the AT&T foundation and NSF grant DCR-8351757.Primarily supported by a 1967 Science and Engineering Scholarship from the Natural Sciences and Engineering Research Council of Canada.     

Minimum congestion spanning trees in planar graphs

The main purpose of the paper is to develop an approach to the evaluation or the estimation of the spanning tree congestion of planar graphs. This approach is used to evaluate the spanning tree congestion of triangular grids.     

Undirected simple connected graphs with minimum number of spanning trees

We show that for positive integers n, m with n(n−1)/2≥m≥n−1, the graph L_n,m having n vertices and m edges that consists of an (n−k)-clique and k−1 vertices of degree 1 has the fewest spanning trees among all connected graphs on n vertices and m edges. This proves Boesch’s conjecture [F.T. Boesch, A. Satyanarayana, C.L. Suffel, Least reliable networks and reliability domination, IEEE Trans. Commun. 38 (1990) 2004-2009].     

The number of spanning trees in regular graphs

Let C(G) denote the number of spanning trees of a graph G. It is shown that there is a function ?(k) that tends to zero as k tends to infinity such that for every connected, k-regular simple graph G on n vertices C(G) = {k[1 ? δ(G)]}ⁿ. where 0 ≤ δ(G) ≤ ?(k).     

On homeomorphically irreducible spanning trees in cubic graphs

A spanning tree without a vertex of degree two is called a HIST, which is an abbreviation for homeomorphically irreducible spanning tree. We provide a necessary condition for the existence of a HIST in a cubic graph. As one consequence, we answer affirmatively an open question on HISTs by Albertson, Berman, Hutchinson, and Thomassen. We also show several results on the existence of HISTs in plane and toroidal cubic graphs.     

Matchings and spanning trees in Boolean weighted graphs

It is shown that in a 0-sum Boolean weighted graph G the sum of the weights taken over all the spanning trees equals the sum of the weights taken over all the perfect matchings in the graph G − v, where v is any vertex of G. Several related theorems are proved which include parity results on perfect matchings and spanning trees in Eulerian graphs. The ideas on perfect matchings in 0-sum Boolean weighted graphs are generalized to matchings in any Boolean weighted graph.     

Counting spanning trees in prism and anti-prism graphs

In this paper, we calculate the number of spanning trees in prism and antiprism graphs corresponding to the skeleton of a prism and an antiprism. By the electrically equivalent transformations and rules of weighted generating function, we obtain a relationship for the weighted number of spanning trees at the successive two generations. Using the knowledge of difference equations, we derive the analytical expressions for enumeration of spanning trees. In addition, we again calculate the number of spanning trees in Apollonian networks, which shows that this method is simple and effective. Finally we compare the entropy of our networks with other studied networks and find that the entropy of the antiprism graph is larger.