کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4651014 1342516 2006 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On αα-critical edges in König–Egerváry graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On αα-critical edges in König–Egerváry graphs
چکیده انگلیسی

The stability number of a graph G  , denoted by α(G)α(G), is the cardinality of a stable set of maximum size in G  . If α(G-e)>α(G)α(G-e)>α(G), then e   is an αα-critical edge  , and if μ(G-e)<μ(G)μ(G-e)<μ(G), then e   is a μμ-critical edge  , where μ(G)μ(G) is the cardinality of a maximum matching in G. G is a König–Egerváry graph   if its order equals α(G)+μ(G)α(G)+μ(G). Beineke, Harary and Plummer have shown that the set of αα-critical edges of a bipartite graph forms a matching. In this paper we generalize this statement to König–Egerváry graphs. We also prove that in a König–Egerváry graph αα-critical edges are also μμ-critical, and that they coincide in bipartite graphs. For König–Egerváry graphs, we characterize μμ-critical edges that are also αα-critical. Eventually, we deduce that α(T)=ξ(T)+η(T)α(T)=ξ(T)+η(T) holds for any tree T  , and describe the König–Egerváry graphs enjoying this property, where ξ(G)ξ(G) is the number of αα-critical vertices and η(G)η(G) is the number of αα-critical edges.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 306, Issue 15, 6 August 2006, Pages 1684–1693
نویسندگان
, ,