Fractional matchings and the Edmonds-Gallai theorem
type: Item
instance of: scholarly article
title: Fractional matchings and the Edmonds-Gallai theorem
zbMATH Open document ID: 0637.05019
DOI: 10.1016/0166-218X(87)90053-9
published in: Discrete Applied Mathematics
publication date: 1987-01-01T00:00:00Z
review text: A fractional matching of a graph is an assignment of the values 0, 1/2, 1 to the edges of the graph in such a way that for each node, the sum of the values on the incident edges is at most 1. This note shows that the Edmonds-Gallai structure theorem for maximum matchings in graphs provides a structural characterization for the class of maximum fractional matchings for which the number of cycles in the support is minimum. This in turn provides an easy derivation for the class of maximum fractional matchings for which the number of edges assigned the value 1 is maximized.
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 4037888
zbMATH Keywords: graph characterization
zbMATH Keywords: Edmonds-Gallai structure theorem
zbMATH Keywords: maximum fractional matchings
author: William R. Pulleyblank
MaRDI profile type: Publication
cites work: Integer and Fractional Matchings
cites work: Q5635469
cites work: An extension of matching theory
cites work: Packing subgraphs in a graph
cites work: Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem
cites work: Paths, Trees, and Flowers
cites work: Transversals and matroid partition
cites work: Q3270978
cites work: Q4130999
cites work: Q4405192
cites work: F-factors of graphs: A generalized matching problem
cites work: On certain classes of fractional matchings
cites work: Q4739657
cites work: Q4078069
cites work: The Factors of Graphs
cites work: Q4133438
Recommended article: On certain classes of fractional matchings
Recommended article: Fractional Gallai-Edmonds decomposition and maximal graphs on fractional matching number
Recommended article: Fractional matchings in hypergraphs
Recommended article: Fractional Matchings of Graphs
Recommended article: Fractional matroid matchings
Recommended article: Q3199198
Recommended article: The fractional matching numbers of graphs
Recommended article: Fractional and integer matchings in uniform hypergraphs
Recommended article: A note on maximum fractional matchings of graphs
description: scientific article; zbMATH DE number 4037888