Maximum matchings of a digraph based on the largest geometric multiplicity
type: Item
instance of: scholarly article
title: Maximum matchings of a digraph based on the largest geometric multiplicity
zbMATH Open document ID: 1400.05190
DOI: 10.1155/2016/4702387
author: Yunyun Yang
author: Gang Xie
published in: Mathematical Problems in Engineering
publication date: 2018-10-12T00:00:00Z
review text: Summary: 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.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C50
zbMATH DE Number: 6953218
Wikidata QID: Q59131367
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2016/4702387
OpenAlex ID: W2345051985
cites work: Digraphs
cites work: Optimal node ranking of tree in linear time
cites work: Rankings of Graphs
cites work: Random Walks on Infinite Graphs and Groups
cites work: Assignment Problems
cites work: Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
cites work: Q5199685
cites work: The labeled maximum matching problem
cites work: Matrix Analysis
cites work: The minimum cost perfect matching problem with conflict pair constraints
cites work: The isomorphism problem for rose window graphs
cites work: The minimal Laplacian spectral radius of trees with given matching number
cites work: Maximum induced matchings close to maximum matchings
cites work: Mathematical Description of Linear Dynamical Systems
cites work: Q5582663
description: scientific article; zbMATH DE number 6953218