The Wiener index for path, star, cycle and wheel graphs

Given a graph G=(V, E), the Wiener index has two equivalent definitions:

Where d(i,j) is the shortest path between the two nodes.

Resources: Wikipedia, Mathworld.

Note: The summation series are used in the calculation.

The path graph

For this graph is easier to use the second formula that requires an ordering of the nodes. We assume that the nodes are ordered from left to right. The second formulas ask us to pick a node, find the shortest paths between all the node’s successors, and sum them.

The initial step of an example for n=5, where the numbers are the weight of the shortest path.

From this, we can deduce that the index is the sum of consecutive numbers.

We could also see it in another way:

Obtaining:

The two formulas are equivalent, but we will use the second since the calculation is shorter.

The star graph

For this graph is better to use the first definition of the Wiener index. The characteristic of this graph is that the node at the center can reach all the other nodes in one step.

star graph with n=5, focus on the central node

For all the n-1 leaves, the situation is the same:

star graph with n=5, focus on a leaf

So the sum of the distances is:

Then for obtaining the index, we remove the initial number two:

The cycle graph

There are two cases to consider: when n is odd and when n is even.

In the case where n is odd, the graph needs to have at least three nodes. In the image, an example with seven nodes where it’s possible to notice the symmetry:

cycle graph with n = 7

So for every node, there are half of the n-1 nodes at increasing distances.

The case when n is even is similar, but we require n ≥ 4 .

The example with n=6 .

cycle graph with n = 6

For every node, there is the double of the summation plus the opposite node.

The wheel graph

In this graph, the central node can reach every node in one step, while every other node can reach the rest of the nodes in less than two edges.

wheel graph with n=7

So the Wiener index it’s formed by the sum of two cases:

• the case for the outside nodes that are n-1 where that node is adjacent to 3 other nodes and can reach all the others in 3 moves;
• the case for the central node that can reach all the other n-1 nodes in one step.

The formula shows that it’s necessary that n≥4.