TOPICS

Independence Number

The (upper) vertex independence number of a graph, 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 , but may also be written (e.g., Burger et al. 1997) or (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 may be similarly defined as the size of a smallest maximal independent vertex set in (Burger et al. 1997).

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

 (1)

(Burger et al. 1997).

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

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

 (2)

For a connected regular graph on vertices with vertex degree and smallest graph eigenvalue ,

 (3)

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

 (4)

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

 (5)

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

The matching number of a graph is equal to the independence number of its line graph .

By definition,

 (6)

where is the vertex cover number of and its vertex count (West 2000).

Known value for some classes of graph are summarized below.

 graph OEIS values alternating group graph A000000 1, 1, 4, 20, 120, ... -Andrásfai graph () A000027 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ... -antiprism graph () A004523 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 10, ... -Apollonian network A000244 1, 3, 9, 27, 81, 243, 729, 2187, ... complete bipartite graph A000027 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ... complete graph 1 A000012 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... complete tripartite graph A000027 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ... cycle graph () A004526 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, ... empty graph A000027 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ... -folded cube graph () A058622 1, 1, 4, 5, 16, 22, 64, 93, 256, ... grid graph A000982 1, 2, 5, 8, 13, 18, 25, 32, 41, 50, 61, 72, ... grid graph A036486 1, 4, 14, 32, 63, 108, 172, 256, 365, 500, ... -halved cube graph A005864 1, 1, 4, 5, 16, 22, 64, 93, 256, ... -Hanoi graph A000244 1, 3, 9, 27, 81, 243, 729, 2187, ... hypercube graph A000079 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ... -Keller graph A258935 4, 5, 8, 16, 32, 64, 128, 256, 512, ... -king graph () A008794 1, 4, 4, 9, 9, 16, 16, 25, 25 -knight graph () A030978 4, 5, 8, 13, 18, 25, 32, 41, 50, 61, 72, ... Kneser graph -Mycielski graph A266550 1, 1, 2, 5, 11, 23, 47, 95, 191, 383, 767, ... Möbius ladder () A109613 3, 3, 5, 5, 7, 7, 9, 9, 11, 11, 13, 13, 15, ... odd graph A000000 1, 1, 4, 15, 56, 210, 792, 3003, 11440, ... -pan graph A000000 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, ... path graph A004526 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, ... prism graph () A052928 2, 4, 4, 6, 6, 8, 8, 10, 10, 12, 12, ... -Sierpiński carpet graph 4, 32, 256, ... -Sierpiński gasket graph 1, 3, 6, 15, 42, ... star graph A028310 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ... triangular graph () A004526 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, ... -web graph () A032766 4, 6, 7, 9, 10, 12, 13, 15, 16, 18, 19, 21, ... wheel graph A004526 1, 2, 2, 3, 3, 4, 4, 5, 5, ...

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

Clique 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

More things to try:

References

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.

Referenced on Wolfram|Alpha

Independence Number

Cite this as:

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