Maximum Matchings of a Digraph Based on the Largest Geometric Multiplicity

Yunyun Yang and Gang Xie

Mathematical Problems in Engineering, 2016, vol. 2016, 1-7

Abstract:

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.

Date: 2016
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/MPE/2016/4702387.pdf (application/pdf)
http://downloads.hindawi.com/journals/MPE/2016/4702387.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnlmpe:4702387

DOI: 10.1155/2016/4702387

Access Statistics for this article

More articles in Mathematical Problems in Engineering from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().