TOPICS
Search

Independence Number

DOWNLOAD Mathematica NotebookDownload 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

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

(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,

alpha(G)=omega(G^_).
(2)

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

alpha<=(n(-s))/(k-s)
(3)

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

For r the graph radius,

alpha>=r
(4)

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

alpha>=rho,
(5)

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,

alpha(G)+tau(G)=|G|,
(6)

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

alpha(G)=max_(w_i+w_j<=1 for e_(ij) in E; w_i in {0,1})sum_(v in V)w_i
(7)

where w_i=w(v_i) is the weight on the ith 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 GraphData[graph, "IndependenceNumber"].

Known value for some classes of graph are summarized below.

graph Galpha(G)OEISvalues
alternating group graph AG_nA0000001, 1, 4, 20, 120, ...
n-Andrásfai graph (n>=3)nA0000273, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
n-antiprism graph (n>=3)|_2n/3_|A0045232, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 10, ...
n-Apollonian network3^(n-1)A0002441, 3, 9, 27, 81, 243, 729, 2187, ...
complete bipartite graph K_(n,n)nA0000271, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
complete graph K_n1A0000121, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
complete tripartite graph K_(n,n,n)nA0000271, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
cycle graph C_n (n>=3)|_n/2_|A0045261, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, ...
empty graph K^__nnA0000271, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
n-folded cube graph (n>=2)2^(n-2)-1/4(1-(-1)^n)(n-1; (n-1)/2)A0586221, 1, 4, 5, 16, 22, 64, 93, 256, ...
grid graph P_n square P_n[n^2/2]A0009821, 2, 5, 8, 13, 18, 25, 32, 41, 50, 61, 72, ...
grid graph P_n square P_n square P_n[n^3/2]A0364861, 4, 14, 32, 63, 108, 172, 256, 365, 500, ...
n-halved cube graphA0058641, 1, 4, 5, 16, 22, 64, 93, 256, ...
n-Hanoi graph3^(n-1)A0002441, 3, 9, 27, 81, 243, 729, 2187, ...
hypercube graph Q_n2^(n-1)A0000791, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ...
n-Keller graph{4 for n=1; 5 for n=2; 2^n otherwiseA2589354, 5, 8, 16, 32, 64, 128, 256, 512, ...
(n,n)-king graph (n>=2)|_(n+1)/2_|^2A0087941, 4, 4, 9, 9, 16, 16, 25, 25
(n,n)-knight graph (n>=2){4 for n=2; (1+(-1)^(n+1)+2n^2)/4 otherwiseA0309784, 5, 8, 13, 18, 25, 32, 41, 50, 61, 72, ...
Kneser graph K(n,k)(n-1; k-1)
n-Mycielski graph{1 for n=1,2; 3·2^(n-3)-1 otherwiseA2665501, 1, 2, 5, 11, 23, 47, 95, 191, 383, 767, ...
Möbius ladder M_n (n>=3)2[n/2]-1A1096133, 3, 5, 5, 7, 7, 9, 9, 11, 11, 13, 13, 15, ...
odd graph O_n{1 for n=1; (2n-2; n-2) otherwiseA0000001, 1, 4, 15, 56, 210, 792, 3003, 11440, ...
n-pan graph1+|_n/2_|A0000002, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, ...
path graph P_n[n/2]A0045261, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, ...
prism graph Y_n (n>=3)2|_n/2_|A0529282, 4, 4, 6, 6, 8, 8, 10, 10, 12, 12, ...
n-Sierpiński carpet graph4, 32, 256, ...
n-Sierpiński gasket graph1, 3, 6, 15, 42, ...
star graph S_n{1 for n=1; n-1 otherwiseA0283101, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
triangular graph T_n (n>=2)|_n/2_|A0045261, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, ...
n-web graph (n>=3)1/4[6n+(-1)^n-1]/4A0327664, 6, 7, 9, 10, 12, 13, 15, 16, 18, 19, 21, ...
wheel graph W_n|_(n-1)/2_|A0045261, 2, 2, 3, 3, 4, 4, 5, 5, ...

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 Web Resource. https://mathworld.wolfram.com/IndependenceNumber.html

Subject classifications