ملخص
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 |
المعرِّفات الرقمية للأشياء | |
حالة النشر | نُشِر - 2020 |