Minimal Spanning Tree of Weighted Parametrised Graph

I have been recently teaching Graph Theory to second year students. Amongst the things we covered in class were minimal spanning trees. The topic inspired me the following problem.

Let us consider a fully connected graph G with N vertex all labelled from 1 to N. A weight w(e_{i,j}) is associated to each edge e_{i,j}. We define


with a and b real numbers.

Depending of the values of a and b, what can we say about the minimal spanning tree of G ? Is it unique ? If not how many spanning trees are there ?


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s