کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419430 683803 2012 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Local maximum stable set greedoids stemming from very well-covered graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Local maximum stable set greedoids stemming from very well-covered graphs
چکیده انگلیسی

A maximum stable set  in a graph GG is a stable set of maximum cardinality. The set SS is called a local maximum stable set   of GG, and we write S∈Ψ(G)S∈Ψ(G), if SS is a maximum stable set of the subgraph induced by the closed neighborhood of SS. A greedoid (V,F)(V,F) is called a local maximum stable set greedoid   if there exists a graph G=(V,E)G=(V,E) such that F=Ψ(G)F=Ψ(G).Nemhauser and Trotter Jr. (1975) [28] proved that any S∈Ψ(G)S∈Ψ(G) is a subset of a maximum stable set of GG. In Levit and Mandrescu (2002) [16] we showed that the family Ψ(T)Ψ(T) of a forest TT forms a greedoid on its vertex set. The cases where GG is bipartite, triangle-free, and well-covered while Ψ(G)Ψ(G) is a greedoid were analyzed in Levit and Mandrescu (2004) [18], Levit and Mandrescu (2007) [20], and Levit and Mandrescu (2008) [23], respectively.In this paper we demonstrate that if GG is a very well-covered graph, then the family Ψ(G)Ψ(G) is a greedoid if and only if GG has a unique perfect matching.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 160, Issue 12, August 2012, Pages 1864–1871
نویسندگان
, ,