When a bipartite complete graph Km,n is given, two subgraphs of Km,n are in the same class when the degree of each right vertex coincides. I want to know the number of all spanning trees in a given class.
Any spanning tree in Km,n has M+N-1 edges. A class whose right degrees do not sum up to M+N-1 does not contain any spanning tree. The number of classes with total degree M+N-1 is the repeated combination of country labels taken N -1 times. Thus the number take the form
(M + N - 2)! / (M - 1)! (N -1)! .
From Scoins' formula the number of all spanning trees in Km,n is
MN-1 ・NM-1 .
As a consequence, there are in general many spanning trees in a class in which the right degrees sum up to M+N-1. I want to know an explicit formula that gives the number of all spanning trees for a given class with degree sum M + N -1.
This question is derived in the course of Ricardian trade theory study.
For an illustration, I show some simple cases for small M and N.
(1) 2×2 case
K2,2 (complete bipartite graph) has 4 spanning trees. Let the set of country labels {A, B} and the set of goods {1,2}. Then the fours trees are
{A12, B1} , {A12, B2}, {A1, B12}, {A2, B12} .
Note: {A12, B1} show that edges are {A1, A2, B1}. They are sometimes more simply expressed as {12, 1}. I prefer to conserve country labels A and B.
A (left) class in 2-country 2-good economy is a set of degrees {di} for all countries. Any spanning trees in K2,2 has M+N-1 edges. Therefore we are interested in the case:
d1 + d2 = 2 + 2 -1 = 3.
In addition, di must be equal or bigger than 1. Then there are only 2 spanning classes:
{2,1} and {1,2}.
It is easy to see that in this case two classes have the same number of spanning trees:
{A12, B1} , {A12, B2} belong to class {2,1}.
{A1, B12}, {A2, B12} belong to class {1,2}.
(2) 2×3 case
There are 12 spanning trees belonging to one of 3 classes:
class {3,1}: {A123, B1}. {A123, B2}, {A123, B3}
class{2,2}: {A12, B13}, {A12, B23}, {A13, B12}, {A13, B23}, {A23, B12}, {A23, B13}
class{1,3}: {A1, B123}, {A2, B123}, {A3, B123}
It is clear that classes contain different number of spanning trees.
I want to know an explicit formula for the function
H(d1, d2, ... , dM),
when H(c) is the number of all spanning trees which belongs to class
c = {d1, d2, ... , dM} .
Those who are interested how this question is related to Ricardian trade theory are required to read some of my answers in the question page (fourth post in particular):
A Conjecture on Trees in a Complete Bipartite Graph: does two trees of the same class have a cycle with opposite orientations?
https://www.researchgate.net/post/A_Conjecture_on_Trees_in_a_Complete_Bipartite_Graph_does_two_trees_of_the_same_class_have_a_cycle_with_opposite_orientations/1
A Discussion in another question may also help you. See sixth answer in particular. Why did Eaton and Kortum model perform so badly?
https://www.researchgate.net/post/Why_did_Eaton_and_Kortum_model_perform_so_badly
Do you know the number of all spanning trees of a given class? - ResearchGate. Available from: https://www.researchgate.net/post/Do_you_know_the_number_of_all_spanning_trees_of_a_given_class [accessed Sep 23, 2015].
I'm guessing that an explicit formula may be difficult (if not impossible) as the number of classes is related to the composition number for n+m. I think a simple recursion might be possible. Let me think on it and get bck to you.
Dear Robert A. Beeler,
thank you for your comment. I am expecting to hear from you good news.
Shiozawa
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs