Premium
Graphs with the balas—uhry property
Author(s) -
Kano M.,
Poljak S.
Publication year - 1990
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190140512
Subject(s) - combinatorics , mathematics , matching (statistics) , graph , induced subgraph , property (philosophy) , order (exchange) , discrete mathematics , induced subgraph isomorphism problem , line graph , statistics , voltage graph , philosophy , epistemology , finance , vertex (graph theory) , economics
We characterize graphs H with the following property: Let G be a graph and F be a subgraph of G such that (i) each component of F is isomorphic to H or K 2 , (ii) the order of F is maximum, and (iii) the number of H ‐components in F is minimum subject to (ii). Then a maximum matching of F is also a maximum matching of G. This result is motivated by an analogous property of fractional matchings discovered independently by J. P. Uhry and E. Balas.