Premium
The fractional matching numbers of graphs
Author(s) -
Liu Yan,
Liu Guizhen
Publication year - 2002
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10047
Subject(s) - combinatorics , mathematics , matching (statistics) , infimum and supremum , vertex (graph theory) , graph , discrete mathematics , statistics
A fractional matching of a graph G is a function f that assigns to each edge a number in [0, 1] such that, for each vertex v , ∑ f ( e ) ≤ 1, where the sum is taken over all edges incident to v . The fractional matching number of G is the supremum of ∑ e ∈ E ( G ) f ( e ) over all fractional matchings f . In this paper, we provide a new formula for calculating the fractional matching numbers of graphs using the Gallai–Edmonds Structure Theorem. Thus, we characterize graphs for which the fractional matching number equals the matching number and graphs for which the fractional matching number is the maximum possible (one‐half the number of vertices). © 2002 Wiley Periodicals, Inc.