Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650613 | Discrete Mathematics | 2006 | 13 Pages |
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).