Maximum matchings of a digraph based on the largest geometric multiplicity
Joint Authors
Source
Mathematical Problems in Engineering
Issue
Vol. 2016, Issue 2016 (31 Dec. 2016), pp.1-7, 7 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2016-04-28
Country of Publication
Egypt
No. of Pages
7
Main Subjects
Abstract EN
Matching theory is one of the most forefront issues of graph theory.
Based on the largest geometric multiplicity, we develop an efficient approach to identify maximum matchings in a digraph.
For a given digraph, it has been proved that the number of maximum matched nodes has close relationship with the largest geometric multiplicity of the transpose of the adjacency matrix.
Moreover, through fundamental column transformations, we can obtain the matched nodes and related matching edges.
In particular, when a digraph contains a cycle factor, the largest geometric multiplicity is equal to one.
In this case, the maximum matching is a perfect matching and each node in the digraph is a matched node.
The method is validated by an example.
American Psychological Association (APA)
Yang, Yunyun& Xie, Gang. 2016. Maximum matchings of a digraph based on the largest geometric multiplicity. Mathematical Problems in Engineering،Vol. 2016, no. 2016, pp.1-7.
https://search.emarefa.net/detail/BIM-688947
Modern Language Association (MLA)
Yang, Yunyun& Xie, Gang. Maximum matchings of a digraph based on the largest geometric multiplicity. Mathematical Problems in Engineering No. 2016 (2016), pp.1-7.
https://search.emarefa.net/detail/BIM-688947
American Medical Association (AMA)
Yang, Yunyun& Xie, Gang. Maximum matchings of a digraph based on the largest geometric multiplicity. Mathematical Problems in Engineering. 2016. Vol. 2016, no. 2016, pp.1-7.
https://search.emarefa.net/detail/BIM-688947
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references : p. 6-7
Record ID
BIM-688947