On König-Egerváry collections of maximum critical independent sets

Vadim E. Levit, Eugen Mandrescu

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

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

תקציר

Let G be a simple graph with vertex set V (G). A set S ⊆ V (G) is independent if no two vertices from S are adjacent. Let Ind(G) denote the family of all independent sets. The graph G is said to be König-Egerváry if α (G) + µ (G) = |V (G)|, where α (G) denotes the size of a maximum independent set and µ (G) is the cardinality of a maximum matching. A family Γ ⊆ Ind(G) is a König-Egerváry collection if |S Γ|+ |T Γ| = 2α(G). The number d (X) = |X| − |N(X)| is the difference of X ⊆ V (G), and a set A ∈ Ind(G) is critical if d(A) = max{d (I): I ∈ Ind(G)}. In this paper, we show that if the family of all maximum critical independent sets of a graph G is a König-Egerváry collection, then G is a König-Egerváry graph. This result generalizes one of our conjectures verified by Short in 2016.

שפה מקוריתאנגלית
מספר המאמר1027
כתב עתArt of Discrete and Applied Mathematics
כרך2
מספר גיליון1
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2020

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'On König-Egerváry collections of maximum critical independent sets'. יחד הם יוצרים טביעת אצבע ייחודית.

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