๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Nordhaus-Gaddum inequalities for domination in graphs

โœ Scribed by Frank Harary; Teresa W. Haynes

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
297 KB
Volume
155
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

โœฆ Synopsis

A node in a graph G = (V,E) is said to dominate itself and all nodes adjacent to it. A set S C V is a dominating set for G if each node in V is dominated by some node in S and is a double dominating set for G if each node in V is dominated by at least two nodes in S. First we give a brief survey of Nordhaus-Gaddum results for several domination-related parameters. Then we present new inequalities of this type involving double domination. A direct result of our bounds for double domination in complementary graphs is a new Nordhaus~3addum inequality for open domination improving known bounds for the case when both G and its complement have domination number greater than 4.

๐Ÿ“œ SIMILAR VOLUMES

On a Nordhaus-Gaddum type problem for in
On a Nordhaus-Gaddum type problem for independent domination
โœ E.J. Cockayne; G. Fricke; C.M. Mynhardt ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 254 KB

Let i(G) (i(G), respectively) be the independent domination number (i.e. smallest cardinality of a maximal independent vertex subset) of the p-vertex graph G (the complement G of G, respectively). We prove limp~[max~ i(G)i(Cr)/p 2] = 1/16.

On equality in an upper bound for domina
On equality in an upper bound for domination parameters of graphs
โœ Favaron, O.; Mynhardt, C. M. ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 141 KB ๐Ÿ‘ 2 views

We consider the well-known upper bounds ยต(G) โ‰ค |V (G)|-โˆ†(G), where โˆ†(G) denotes the maximum degree of G and ยต(G) the irredundance, domination or independent domination numbers of G and give necessary and sufficient conditions for equality to hold in each case. We also describe specific classes of gr