Independent Vertex Set

 

 

An independent vertex set of a graph  is a subset of the vertices such that no two vertices in the subset represent an edge of . The figure above shows independent sets consisting of two subsets for a number of graphs (the wheel graph , utility graph , 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  is known as its independence polynomial.

A set of vertices is an independent vertex set iff its complement 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 independent vertex sets. To find all independent vertex sets in the Wolfram Language, enumerate all vertex subsets  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.

graph family	OEIS	number independent vertex sets
antiprism graph for	A000000	X, X, 10, 21, 46, 98, 211, 453, 973, 2090, ...
bishop graph	A201862	X, 9, 70, 729, 9918, 167281, ...
black bishop graph	A000000	X, X, X, 27, 114, 409, 2066, ...
-folded cube graph	A000000	X, 3, 5, 31, 393, ...
grid graph  for	A006506	X, 7, 63, 1234, 55447, 5598861, ...
grid graph  for	A000000	X, 35, 70633, ...
-halved cube graph	A000000	2, 3, 5, 13, 57, ...
-Hanoi graph	A000000	4, 52, 108144, ...
hypercube graph	A027624	3, 7, 35, 743, 254475, 19768832143, ...
king graph	A063443	X, 5, 35, 314, 6427, ...
knight graph	A141243	X, 16, 94, 1365, 55213, ...
-Möbius ladder	A182143	X, X, 15, 33, 83, 197, 479, 1153, 2787, ...
-Mycielski graph	A000000	2, 3, 11, 103, 7407, ...
odd graph	A000000	2, 4, 76, ...
prism graph  for	A051927	X, X, 13, 35, 81, 199, 477, 1155, 2785, ...
queen graph	A000000	2, 5, 18, 87, 462, ...
rook graph	A002720	2, 7, 34, 209, 1546, 13327, 130922, ...
-Sierpiński sieve graph	A000000	4, 14, 440, ...
-triangular graph	A000000	X, 2, 4, 10, 26, 76, 232, 764, ...
-web graph for	A000000	X, X, 68, 304, 1232, 5168, 21408, ...
white bishop graph	A000000	X, X, X, 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,  is a Fibonacci number,  is a Lucas number,  is a Laguerre polynomial,  is the golden ratio, and , ,  are the roots of .

 

graph family	number of independent vertex sets
Andrásfai graph
antiprism graph
book graph
cocktail party graph
complete bipartite graph
complete graph
complete tripartite graph
-crossed prism graph
cycle graph
empty graph
gear graph
helm graph
ladder graph
ladder rung graph
Möbius ladder
pan graph
path graph
prism graph
rook graph
star graph
sun graph
sunlet graph
wheel graph

---

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.

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

Subset

Set Class

Set

Second Category

Proper Subset

Power Set

Matroid

Inductive Set

Independent Set

Graphoid

G_delta Set

First Category