Independence Number

👁 DOWNLOAD Mathematica Notebook
Download Wolfram Notebook

The (upper) vertex independence number of a graph, also known as the 1-packing number, packing number, or stability number (Acín et al. 2016) and often called simply "the" independence number, is the cardinality of the largest independent vertex set, i.e., the size of a maximum independent vertex set (which is the same as the size of a largest maximal independent vertex set). The independence number is most commonly denoted 👁 alpha(G)
, but may also be written 👁 beta(G)
(e.g., Burger et al. 1997) or 👁 beta_0(G)
(e.g., Bollobás 1981).

The independence number of a graph is equal to the largest exponent in the graph's independence polynomial.

The lower independence number 👁 i(G)
may be similarly defined as the size of a smallest maximal 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

(Burger et al. 1997).

The ratio of the independence number of a graph 👁 G
to its vertex count is known as the independence ratio of 👁 G
(Bollobás 1981).

The independence number of a graph 👁 G
is equal to the clique number of the complement graph,

For a connected regular graph 👁 G
on 👁 n>1
vertices with vertex degree 👁 k
and smallest graph eigenvalue 👁 s
,

(A. E. Brouwer, pers. comm., Dec. 17, 2012).

For 👁 r
the graph radius,

(DeLa Vina and Waller 2002). Lovasz (1979, p. 55) showed that when 👁 rho
is the path covering number,

with equality for only complete graphs (DeLa Vina and Waller 2002).

Willis (2011) gives a number of bounds for the independence number of a graph.

The matching number 👁 nu(G)
of a graph 👁 G
is equal to the independence number 👁 alpha(L(G))
of its line graph 👁 L(G)
.

By definition,

where 👁 tau(G)
is the vertex cover number of 👁 G
and 👁 n=|G|
its vertex count (West 2000).

The independence number of a graph 👁 G
with vertex set 👁 V
and edge set 👁 E
may be defined as the result of the integer program

where 👁 w_i=w(v_i)
is the weight on the 👁 i
th vertex. Relaxing this condition to allow 👁 w_i in [0,1]
gives the fractional independence number 👁 alpha^*(G)
.

Precomputed independence numbers for many named graphs can be obtained in the Wolfram Language using [graph, ].

Known value for some classes of graph are summarized below.

See also

Clique Number, Fractional Independence Number, Independence Polynomial, Independence Ratio, Independent Set, Lower Independence Number, Matching Number, Maximum Independent Vertex Set, Minimum Vertex Cover, Shannon Capacity, Vertex Cover

Explore with Wolfram|Alpha

References

Acín, A.; Duan, R.; Roberson, D. E.; Belén Sainz, A.; and Winter, A. "a New Property of the Lovász Number and Duality Relations Between Graph Parameters." 5 Feb 2016. https://arxiv.org/abs/1505.01265.Bollobás, B. "The Independence Ratio of Regular Graphs." Proc. Amer. Math. Soc. 83, 433-436, 1981.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).DeLa Vina, E. and Waller, B. "Independence, Radius and Path Coverings in Trees." Congr. Numer. 156, 155-169, 2002.Lovasz, L. Combinatorial Problems and Exercises. Academiai Kiado, 1979.Skiena, S. "Maximum Independent Set" §5.6.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 218-219, 1990.Sloane, N. J. A. Sequences A000012/M0003, A000027/M0472, A000079/M1129, A000244/M2807, A000982/M1348, A004523, A004526, A005864/M1111, A008794, A028310, A030978, A032766, A036486, A052928, A058622, A109613, A258935, and A266550 West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.Willis, W. "Bounds for the Independence Number of a Graph." Masters thesis. Richmond, VA: Virginia Commonwealth University, 2011.

Referenced on Wolfram|Alpha

Independence Number

Cite this as:

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

Subject classifications