کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650613 | 1632449 | 2006 | 13 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Extremal graphs for a new upper bound on domination parameters in graphs Extremal graphs for a new upper bound on domination parameters in graphs](/preview/png/4650613.png)
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).
Journal: Discrete Mathematics - Volume 306, Issues 19–20, 6 October 2006, Pages 2314–2326