Maximally matched and super matched regular graphs. Issue 2 (2nd April 2016)

• Record Type: Journal Article
• Authors: Lin, Ruizhi; Zhang, Heping
• Is Part Of: International journal of computer mathematics. Volume 1:Issue 2(2016)
• Page Start: 74
• Page End: 84
• Publication Date: 2016-04-02
• Subjects: Regular graph -- integer linear programming -- perfect matching polytope -- matching preclusion -- maximally matched -- super matched; Computer systems -- Periodicals; Computer systems; Periodicals; 004
• DOI: 10.1080/23799927.2016.1249412
• Languages: English
• ISSNs: 2379-9927

Abstract

ABSTRACT: In interconnection networks, matching preclusion is a measure of robustness when there is a link failure. Let G be a graph with an even number of vertices. A set of edges of G is called a matching preclusion set if its deletion from G results in a subgraph that has no perfect matchings, and the one with smallest size is called an optimal matching preclusion set, whose cardinality is called matching preclusion number of G, denoted by . G is maximally matched if is equal to the minimum degree of G and is super matched if every optimal matching preclusion set of G consists of edges incident to a single vertex. In this paper, we present a 0–1 integer linear programming for matching preclusion number of general graph. By using perfect matching polytope we obtain simple characterizations for maximally matched and super matched regular graphs. As their applications, we can derive some known results and show some Cartesian product of regular graphs, such as Hamming graph, hyperstar and star cube, are super matched.