Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6424009 | Electronic Notes in Discrete Mathematics | 2011 | 6 Pages |
Abstract
The independence number of a graph G, denoted by α(G), is the cardinality of an independent set of maximum size in G, while μ(G) is the size of a maximum matching in G, i.e., its matching number. G is a König-Egerváry graph if its order equals α(G)+μ(G). In this paper we give a new characterization of König-Egerváry graphs. We also deduce some properties of vertices belonging to all maximum independent sets of a König-Egerváry graph.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Vadim E. Levit, Eugen Mandrescu,