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).

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

(2)

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

For  the graph radius,

(3)

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

(4)

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,

(5)

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	{4 for n=1; 5 for n=2; 2^n otherwise" src="https://mathworld.wolfram.com/images/equations/IndependenceNumber/Inline61.svg" style="height:93px; width:132px" />	A258935	4, 5, 8, 16, 32, 64, 128, 256, 512, ...
-king graph ()		A008794	1, 4, 4, 9, 9, 16, 16, 25, 25
-knight graph ()	{4 for n=2; (1+(-1)^(n+1)+2n^2)/4 otherwise" src="https://mathworld.wolfram.com/images/equations/IndependenceNumber/Inline67.svg" style="height:65px; width:335px" />	A030978	4, 5, 8, 13, 18, 25, 32, 41, 50, 61, 72, ...
Kneser graph
-Mycielski graph	{1 for n=1,2; 3·2^(n-3)-1 otherwise" src="https://mathworld.wolfram.com/images/equations/IndependenceNumber/Inline71.svg" style="height:61px; width:245px" />	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	{1 for n=1; (2n-2; n-2) otherwise" src="https://mathworld.wolfram.com/images/equations/IndependenceNumber/Inline76.svg" style="height:85px; width:208px" />	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	{1 for n=1; n-1 otherwise" src="https://mathworld.wolfram.com/images/equations/IndependenceNumber/Inline87.svg" style="height:61px; width:157px" />	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"].

---

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 A266550West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.

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

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