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

w(e_{i,j})=a(i+j)+b|i-j|,

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 ?

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s