TY - JOUR
T1 - A Characterization of König-Egerváry Graphs Using a Common Property of All Maximum Matchings
AU - Levit, Vadim E.
AU - Mandrescu, Eugen
PY - 2011/12/1
Y1 - 2011/12/1
N2 - 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.
AB - 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.
KW - Core
KW - Maximum independent set
KW - Maximum matching
UR - http://www.scopus.com/inward/record.url?scp=82955220213&partnerID=8YFLogxK
U2 - 10.1016/j.endm.2011.09.092
DO - 10.1016/j.endm.2011.09.092
M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???
AN - SCOPUS:82955220213
SN - 1571-0653
VL - 38
SP - 565
EP - 570
JO - Electronic Notes in Discrete Mathematics
JF - Electronic Notes in Discrete Mathematics
ER -