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. In this paper we determine the excessive index for mesh, cylinder and torus networks. © 2014 Elsevier B.V.

Indra Rajasingh

Mathematics

School of Advanced Sciences

Chennai Campus

Shanthi A.S

Muthumalai A.

Fulltext

Vellore Institute of Technology (VIT) is a private university located in&nbsp;Tamil Nadu, India. Founded in 1984, as Vellore Engineering College, the institution offers 20 undergraduate, 34 postgraduate, four integrated and four research programs. It has campuses in Vellore, Amravati, Bhopal and Chennai.

VIT is one of the top ranked private universities in India according to NIRF, THE and QS Rankings.&nbsp;Govt. of India has recognized&nbsp;VIT, Vellore as an&nbsp;Institution of Eminence. This has allowed VIT to take independent quality initiatives and move up in world ranking.

&nbsp;

&nbsp;

VIT University

Journal of Discrete Algorithms

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. © 2013 Elsevier B.V.

Theoretical Computer Science

On excessive index of certain networks

The structural formulae of chemical compounds are molecular graphs where vertices represent atoms and edges represent chemical bonds. A kekule structure in a molecular graph is nothing but a perfect matching in the graph. The minimum number of kekule structures that cover the edge set of a molecular graph G is known as the excessive index of G. In this paper we determine the excessive index of the unit cell representation of sodium chloride and 3-D mesh networks representing oxides and selenides of certain chemical compounds. Further we determine the excessive index of hexagonal networks. © 2013 Academic Publications, Ltd.

Journal	Data powered by TypesetJournal of Discrete Algorithms
Publisher	Data powered by TypesetElsevier BV
ISSN	1570-8667
Open Access	Yes