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

بصمة

أدرس بدقة موضوعات البحث “On König-Egerváry collections of maximum critical independent sets'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا