Number of spanning trees in a complete split graph

Question

A graph is a complete split graph if we can partition it into an independent vertex set and a clique, such that every vertex of the independent vertex set is adjacent to every vertex in the clique.

How can I count the number of spanning trees in such a graph?

Update:

Using a little bit of sagemath code, I can get the spanning tree count for complete split graphs.

Sage code:

def complete_split_graph(order_of_indep_set, order_of_clique):
    G = graphs.CompleteGraph(order_of_clique)
    clique_vertices = G.vertices()
    for i in range(order_of_indep_set):
        new_vertex = 'i'+str(i)
            for v in clique_vertices:
                G.add_edge(new_vertex, v)
    return G

for i in range(1, 6):
    for c in range(1, 6):
        KS = complete_split_graph(i, c)
        span_tree_count = KS.spanning_trees_count()
        print "$\\tau(\\textrm{{KS}}_{{ {},{} }})$ = {}; ".format(i, c, span_tree_count)

Running the code I get the following results, where $KS_{i, j}$ denotes a complete split graph with an independent set of order $i$ and a clique of order $j$, and $\tau(G)$ denotes the number of spanning trees in a graph $G$:

$\tau(\textrm{KS}_{ 1,1 })$ = 1; $\tau(\textrm{KS}_{ 1,2 })$ = 3; $\tau(\textrm{KS}_{ 1,3 })$ = 16; $\tau(\textrm{KS}_{ 1,4 })$ = 125; $\tau(\textrm{KS}_{ 1,5 })$ = 1296; $\tau(\textrm{KS}_{ 2,1 })$ = 1; $\tau(\textrm{KS}_{ 2,2 })$ = 8; $\tau(\textrm{KS}_{ 2,3 })$ = 75; $\tau(\textrm{KS}_{ 2,4 })$ = 864; $\tau(\textrm{KS}_{ 2,5 })$ = 12005; $\tau(\textrm{KS}_{ 3,1 })$ = 1; $\tau(\textrm{KS}_{ 3,2 })$ = 20; $\tau(\textrm{KS}_{ 3,3 })$ = 324; $\tau(\textrm{KS}_{ 3,4 })$ = 5488; $\tau(\textrm{KS}_{ 3,5 })$ = 102400; $\tau(\textrm{KS}_{ 4,1 })$ = 1; $\tau(\textrm{KS}_{ 4,2 })$ = 48; $\tau(\textrm{KS}_{ 4,3 })$ = 1323; $\tau(\textrm{KS}_{ 4,4 })$ = 32768; $\tau(\textrm{KS}_{ 4,5 })$ = 820125; $\tau(\textrm{KS}_{ 5,1 })$ = 1; $\tau(\textrm{KS}_{ 5,2 })$ = 112; $\tau(\textrm{KS}_{ 5,3 })$ = 5184; $\tau(\textrm{KS}_{ 5,4 })$ = 186624; $\tau(\textrm{KS}_{ 5,5 })$ = 6250000;

However, I am not satisfied with my way of doing it. I would prefer to find a formula, and I'd like to know how to do it without a computer doing the work for me. So I'd appreciate further hints and help.

Answer 1

An alternative would be to use Prufer sequences. (If you don't know what these are, I suggest you look them up, and how they can be used to prove Cayley's formula before reading the rest of this hint).

Write $A$ for the largest independent set in the split graph, and $B$ for the vertex set of the largest clique. Consider the following algorithm for converting a spanning tree in the split graph into two strings, $s_A$ and $s_B$. At step i, pick the leaf with the smallest label. If this leaf is in $A$, append the label of its neighbour to $s_A$. Otherwise, append the label of its neighbour to $s_B$. Delete this leaf from the tree, and repeat until there are only 2 vertices. Can you choose the enumeration of vertices such that you are guaranteed that one of these vertices is in $A$? How long will $s_A$ and $s_B$ be in this process, and what are the possiblities for each? Now come up with a reverse process to convert between 'allowed string pairs' and spanning trees.

This method should give you a nice one term formula for the number of spanning trees.