Advances and Applications in Discrete Mathematics
Volume 19, Issue 1, Pages 61 - 70
(January 2018) http://dx.doi.org/10.17654/AADMJan2018_061_070 |
|
DUALITY AND HEREDITARY KÖNIG-EGERVÁRY SET-SYSTEMS
Adi Jarden
|
Abstract: A König-Egerváry graph is a graph G satisfying where is the cardinality of a maximum independent set and is the matching number of G. Such graphs are those that admit a matching between and where G is a set-system comprised of maximum independent sets satisfying for every set-system in order to improve this characterization of a König-Egerváry graph, we characterize hereditary König-Egerváry set-systems (HKE set-systems, hereafter).
An HKE set-system is a set-system, F, such that for some positive integer, a, the equality holds for every non-empty subset, G, of F.
We prove the following theorem: Let F be a set-system. F is an HKE set-system if and only if the equality holds for every two non-empty disjoint subsets, of F. Consequently, we get a new characterization of a König-Egerváry graph. This theorem is applied in [2] and is a key point in [1], where we get a better characterization of a König-Egerváry graph. |
Keywords and phrases: König-Egerváry graph, maximum independent set, hereditary König-Egerváry set-systems. |
|
Number of Downloads: 356 | Number of Views: 4380 |
|