Maximally matched and super matched regular graphs. Issue 2 (2nd April 2016)
- Record Type:
- Journal Article
- Title:
- Maximally matched and super matched regular graphs. Issue 2 (2nd April 2016)
- Main Title:
- Maximally matched and super matched regular graphs
- Authors:
- Lin, Ruizhi
Zhang, Heping - 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.
- Is Part Of:
- International journal of computer mathematics. Volume 1:Issue 2(2016)
- Journal:
- International journal of computer mathematics
- Issue:
- Volume 1:Issue 2(2016)
- Issue Display:
- Volume 1, Issue 2 (2016)
- Year:
- 2016
- Volume:
- 1
- Issue:
- 2
- Issue Sort Value:
- 2016-0001-0002-0000
- 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 - Journal URLs:
- http://www.tandfonline.com/loi/tcom20 ↗
http://www.tandfonline.com/ ↗ - DOI:
- 10.1080/23799927.2016.1249412 ↗
- Languages:
- English
- ISSNs:
- 2379-9927
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - BLDSS-3PM
British Library STI - ELD Digital store - Ingest File:
- 2650.xml