תקציר
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 |