Critical Sets in Bipartite Graphs

Vadim E. Levit, Eugen Mandrescu

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

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

תקציר

Let G = (V, E) be a graph. A set I ⊆ V is independent if no two vertices from I are adjacent, and by Ind(G) we mean the family of all independent sets of G, while core(G) is the intersection of all maximum independent sets [4]. The number dc(G) = max{{pipe}I{pipe} - {pipe}N(I){pipe}: I ∈ Ind(G)} is called the critical difference of G. A set X is critical if {pipe}X{pipe} - {pipe}N(X){pipe} = dc(G) [10]. For a bipartite graph G = (A, B, E), Ore [7] defined δ0(A) = max{{pipe}X{pipe} - {pipe}N(X){pipe}: X ⊆ A}. In this paper, we prove that dc(G) = δ0(A)+δ0(B) and ker(G) = core(G) hold for every bipartite graph G = (A, B, E), where ker(G) denotes the intersection of all critical independent sets.

שפה מקוריתאנגלית
עמודים (מ-עד)543-548
מספר עמודים6
כתב עתAnnals of Combinatorics
כרך17
מספר גיליון3
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - ספט׳ 2013

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Critical Sets in Bipartite Graphs'. יחד הם יוצרים טביעת אצבע ייחודית.

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