کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650613 1632449 2006 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Extremal graphs for a new upper bound on domination parameters in graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Extremal graphs for a new upper bound on domination parameters in graphs
چکیده انگلیسی

In 1958, Claude Berge studied the domination number γ(G)γ(G) of a graph and showed that every graph G=(V,E)G=(V,E) satisfies γ(G)⩽|V|-maxd(v)γ(G)⩽|V|-maxd(v), where d(v)d(v) is the degree of vertex vv. We show here that every graph G   satisfies the inequality ψ(G)⩽|V|-d(v)-βv(G)ψ(G)⩽|V|-d(v)-βv(G), where ψ(G)ψ(G) stands for any of the three parameters ir(G)ir(G) (irredundance number), γ(G)γ(G) (domination number) and i(G)i(G) (size of a smallest maximal independent set), and βv(G)βv(G) is the size of a largest matching in the subgraph of G   induced by the non-neighbours of vv. This improves on Berge's and other inequalities. We then give a characterization of the trees T   that achieve equality in the above inequality for the parameters i(T)i(T) and γ(T)γ(T), and of the regular graphs G   that achieve equality for γ(G)γ(G).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 306, Issues 19–20, 6 October 2006, Pages 2314–2326
نویسندگان
, , ,