TOPICS
Search

Independent Vertex Set

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
IndependentSet

An independent vertex set of a graph G, also known as a stable set, is a subset of the vertices such that no two vertices in the subset are joined by an edge of G. The figure above shows independent sets consisting of two subsets for a number of graphs (the wheel graph W_8, utility graph K_(3,3), Petersen graph, and Frucht graph).

Any independent vertex set is an irredundant set (Burger et al. 1997, Mynhardt and Roux 2020).

The polynomial whose coefficients give the number of independent vertex sets of each cardinality in a graph G is known as its independence polynomial.

A set of vertices is an independent vertex set iff its complement set forms a vertex cover (Skiena 1990, p. 218). The counts of vertex covers and independent vertex sets in a graph are therefore the same.

The empty set is trivially an independent vertex set since it contains no vertices, and therefore no edge endpoints.

A maximum independent vertex set is an independent vertex set of a graph containing the largest possible number of vertices for the given graph, and the cardinality of this set is called the independence number of the graph.

An independent vertex set that cannot be enlarged to another independent vertex set by adding a vertex is called a maximal independent vertex set.

In the Wolfram Language, the command FindIndependentVertexSet[g][[1]] can be used to find a maximum independent vertex set, and FindIndependentVertexSet[g, Length /@ FindIndependentVertexSet[g], All] to find all maximum independent vertex sets. Similarly, FindIndependentVertexSet[g, Infinity] can be used to find a maximal independent vertex set, and FindIndependentVertexSet[g, Infinity, All] to find all maximal independent vertex sets. To find all independent vertex sets in the Wolfram Language, enumerate all vertex subsets s and select those for which IndependentVertexSetQ[g, s] is true.

Independent vertex set counts for some families of graphs are summarized in the following table. The index of each value list in the table starts at 1. An X indicates that the family in that row is not defined for the corresponding parameter value.

graph familyOEISnumber independent vertex sets
antiprism graph for n>=3X, X, 10, 21, 46, 98, 211, 453, 973, 2090, ...
n×n bishop graphA2018622, 9, 70, 729, 9918, 167281, ...
n×n black bishop graph2, 3, 10, 27, 114, 409, 2066, ...
n-folded cube graphX, 3, 5, 31, 393, ...
grid graph P_n square P_n for n>=2A006506X, 7, 63, 1234, 55447, 5598861, ...
grid graph P_n square P_n square P_n for n>=2X, 35, 70633, ...
n-halved cube graph2, 3, 5, 13, 57, ...
n-Hanoi graph4, 52, 108144, ...
hypercube graph Q_nA0276243, 7, 35, 743, 254475, 19768832143, ...
n×n king graphA0634432, 5, 35, 314, 6427, ...
n×n knight graphA1412432, 16, 94, 1365, 55213, ...
n-Möbius ladderA182143X, X, 15, 33, 83, 197, 479, 1153, 2787, ...
n-Mycielski graph2, 3, 11, 103, 7407, ...
odd graph O_n2, 4, 76, ...
prism graph Y_n for n>=3A051927X, X, 13, 35, 81, 199, 477, 1155, 2785, ...
n×n queen graph2, 5, 18, 87, 462, ...
n×n rook graphA0027202, 7, 34, 209, 1546, 13327, 130922, ...
n-Sierpiński gasket graph4, 14, 440, ...
n-triangular graphX, 2, 4, 10, 26, 76, 232, 764, ...
n-web graph for n>=3X, X, 68, 304, 1232, 5168, 21408, ...
n×n white bishop graph1, 3, 7, 27, 87, 409, 1657, ...

Many families of graphs have simple closed forms for counts of independent vertex sets, as summarized in the following table. Here, F_n is a Fibonacci number, L_n is a Lucas number, L_n(x) is a Laguerre polynomial, phi is the golden ratio, and alpha, beta, gamma are the roots of x^3-x^2-2x-1.

graph familynumber of independent vertex sets
Andrásfai graph2^(n-1)(3n-1)+1
antiprism graphalpha^n+beta^n+gamma^n
book graph S_(n+1) square P_23^n+2^(n+1)
cocktail party graph K_(n×2)3n+1
complete bipartite graph K_(n,n)2^(n+1)-1
complete graph K_nn+1
complete tripartite graph K_(n,n,n)3·2^n-2
2n-crossed prism graph2^(-n)[(7-sqrt(21))^n+(7+sqrt(21))^n]
cycle graph C_nL_n
empty graph K^__n2^n
gear graph2^n+(phi+1)^n+(phi+1)^(-n)
helm graph2^n+(1-sqrt(3))^n+(1+sqrt(3))^n
ladder graph1/2[(1-sqrt(2))^(n+1)+(1+sqrt(2))^(n+1)]
ladder rung graph nP_23^n
Möbius ladder M_n(-1)^(n+1)+(1-sqrt(2))^n+(1+sqrt(2))^n
pan graphF_(n+1)+L_n
path graph P_nF_(n+2)
prism graph Y_n(-1)^n+(1-sqrt(2))^n+(1+sqrt(2))^n
n×n rook graphn!L_n(-1)
star graph S_n2^(n-1)+1
sun graph2^(n-2)(n+4)
sunlet graph C_n circledot K_1(1-sqrt(3))^n+(1+sqrt(3))^n
wheel graph W_nL_(n-1)+1

See also

Clique, Disjoint Sets, Edge Cover, Empty Set, Independence Number, Independence Polynomial, Independent Set, Maximal Independent Vertex Set, Maximum Independent Edge Set, Maximum Independent Set Problem, Maximum Independent Vertex Set, Quasi-Kernel, Venn Diagram, Vertex Cover

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.Gallai, T. "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eőtvős Sect. Math. 2, 133-138, 1959.Hochbaum, D. S. (Ed.). Approximation Algorithms for NP-Hard Problems. PWS Publishing, p. 125, 1997.Mynhardt, C. M. and Roux, A. "Irredundance Graphs." 14 Apr. 2020. https://arxiv.org/abs/1812.03382.Myrvold, W. and Fowler, P. W. "Fast Enumeration of All Independent Sets up to Isomorphism." J. Comb. Math. Comb. Comput. 85, 173-194, 2013.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 A002720, A006506, A027624, A051927, A063443, A141243, A182143, and A201862 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Independent Vertex Set

Cite this as:

Weisstein, Eric W. "Independent Vertex Set." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/IndependentVertexSet.html

Subject classifications