TOPICS
Search

Lower Independence Number

The lower independence number i(G) of a graph G is the minimum size of a maximal independent vertex set in G. The lower indepedence number is equivalent to the independent domination number (i.e., the minimum size of an independent dominating set; cf. Crevals and Östergård 2015, Ilić and Milošević 2017).

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

The lower irredundance number ir(G), lower domination number gamma(G), lower independence number i(G), upper independence number alpha(G), upper domination number Gamma(G), and upper irredundance number IR(G) satsify the chain of inequalities

ir(G)<=gamma(G)<=i(G)<=alpha(G)<=Gamma(G)<=IR(G)

(Burger et al. 1997).

See also

Independence Number, Independence Polynomial, Independent Vertex Set

Explore with Wolfram|Alpha

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.Hedetniemi, S. M.; Hedetniemi, S. T.; and Reynolds, R. "Combinatorial Problems on Chessboards: II." In Domination in Graphs: Advanced Topics. Marcel Dekker, p. 141, 1998.Ilić, A. and Milošević, M. "The Parameters of Fibonacci and Lucas Cubes." Ars Math. Contemp. 12, 25-29, 2017.

Cite this as:

Weisstein, Eric W. "Lower Independence Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/LowerIndependenceNumber.html

Subject classifications