Advances and Applications in Discrete Mathematics
Volume 18, Issue 4, Pages 437 - 444
(October 2017) http://dx.doi.org/10.17654/AADMOct2017_437_444 |
|
THE MAXIMUM CARDINALITY OF A HEREDITARY KÖNIG-EGERVÁRY SET-SYSTEM
Adi Jarden
|
Abstract: A set-system F is said to be a Hereditary König-Egerváry (HKE hereafter) set-system, if for some positive integer a, the equality holds for each non-empty subset G of F. The notion of HKE set-systems supplies a new characterization of the König-Egerváry graphs.
We prove that for every two positive integers a and n with the maximal cardinality of an HKE set-system, F, with and is consequently, for every positive integer n, the maximal cardinality of an HKE set-system, F, with is where is the integral value of
We apply these results on graphs. Here is a private case of our main theorem: Let G be a König-Egerváry graph and be the set of maximum independent sets in G. Then where is the size of a set in It is not clear whether this inequality holds for every graph. |
Keywords and phrases: hereditary König-Egerváry set-system, König-Egerváry graph. |
|
Number of Downloads: 311 | Number of Views: 963 |
|