On the number of vertices belonging to all maximum stable sets of a graph

Endre Boros, Martin C. Golumbic, Vadim E. Levit

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

42 ציטוטים ‏(Scopus)

תקציר

Let us denote by α(G) the size of a maximum stable set, and by μ(G) the size of a maximum matching of a graph G, and let ξ(G) be the number of vertices which belong to all maximum stable sets. We shall show that ξ(G)1+α(G)-μ(G) holds for any connected graph, whenever α(G)>μ(G). This inequality improves on related results by Hammer et al. (SIAM J. Algebraic Discrete Methods 3 (1982) 511) and by Levit and Mandrescu [(prE-print math. CO/9912047 (1999) 13pp.)]. We also prove that on one hand, ξ(G)>0 can be recognized in polynomial time whenever μ(G)<|V(G)|/3, and on the other hand determining whether ξ(G)>k is, in general, NP-complete for any fixed k0.

שפה מקוריתאנגלית
עמודים (מ-עד)17-25
מספר עמודים9
כתב עתDiscrete Applied Mathematics
כרך124
מספר גיליון1-3
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 15 דצמ׳ 2002
פורסם באופן חיצוניכן

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'On the number of vertices belonging to all maximum stable sets of a graph'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי