On excessive index of certain networks

Matching is one of the most extensively studied areas in Computer Science and is interesting from the combinatorial point of view as well. A matching in a graph G=(V,E) is a subset M of edges, no two of which have a vertex in common. A matching M is said to be perfect if every vertex in G is an endpoint of one of the edges in M. The excessive index of a graph G is the minimum number of perfect matchings to cover the edge set of G. The study of excessive index has a number of applications particularly in scheduling theory. In this paper we determine the excessive index for certain classes of graphs including augmented butterfly network and honeycomb network. We also prove that the excessive index does not exist for butterfly and Benes networks.