Lower Independence Number

The lower independence number  of a graph  is the minimum size of a maximal independent vertex set in . The lower indepedence number is equiavlent to the "independent domination number" (i.e., the minimum size of an independent dominating set; cf. Crevals and Östergård 2015) since the lower independence number gives the minimum size of a maximal independent vertex set but any maximal independent set is minimal dominating.

The (upper) independence number may be similarly defined as the largest size of an independent vertex set in  (Burger et al. 1997).

The lower independence number , lower domination number , lower independence number , upper independence number , upper domination number , and upper irredundance number  satsify the chain of inequalities

(Burger et al. 1997).

---

REFERENCES

Burger, A. P.; Cockayne, E. J.; and Mynhardt, C. M. "Domination and Irredundance in the Queens' Graph." Disc. Math. 163, 47-66, 1997.

Cockayne, E. J. and Mynhardt, C. M. "The Sequence of Upper and Lower Domination, Independence and Irredundance Numbers of a Graph." Disc. Math. 122, 89-102, 1993).

Crevals, S. and Östergård, P. R. J. "Independent Domination of Grids." Disc. Math. 338, 1379-1384, 2015.

Hedetniemi, S. T. and Laskar, R. C. "A. Bibliography on Dominating Sets in Graphs and Some Basic Definitions of Domination Parameters." Disc. Math. 86, 257-277, 1990.

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength