Abstract

A maximal matching of a graph is the set of edges such that the addition of an edge to this set violates the property of matching (i.e., no two edges of the matching share a vertex). We use the notion of assortative index (ranges from -1 to 1) to evaluate the extent of similarity of the end vertices constituting the edges of a matching. A maximal matching of the edges whose assortative index is as close as possible to 1 is referred to as maximal assortative matching (MAM) and a maximal matching of the edges whose assortative index is as close as possible to -1 is referred to as maximal dissortative matching (MDM). We present algorithms to determine the MAM and MDM of the edges in a network graph. Through extensive simulations, we conclude that random network graphs are more conducive for maximal dissortative matching rather than maximal assortative matching. We observe the assortative index of an MDM on random network graphs to be relatively more closer to the targeted optimal value of -1 compared to the assortative index of an MAM to the targeted optimal value of 1.

This work is licensed under a Creative Commons Attribution 4.0 License.