yields True if the vertex list vlist is an independent vertex set in the graph g, and False otherwise.
- An independent vertex set is a set of vertices that are never incident to the same edge.
- IndependentVertexSetQ works with undirected graphs, directed graphs, multigraphs, and mixed graphs.
Examplesopen allclose all
Basic Examples (2)
IndependentVertexSetQ works with large graphs:
Enumerate all independent vertex sets for a cycle graph:
Enumerate all subsets of vertices and select the ones that are independent vertex sets:
Highlight independent vertex sets:
Enumerate all maximum independent vertex sets for a Petersen graph:
Find the size of a maximum independent vertex set:
Enumerate all maximum independent vertex sets:
Properties & Relations (4)
A largest independent vertex set can be found using FindIndependentVertexSet:
The complement of an independent vertex set is a vertex cover:
The complement subgraph given by an independent vertex set is complete:
Bipartite graphs have equal-length edge covers and independent vertex sets:
Wolfram Research (2010), IndependentVertexSetQ, Wolfram Language function, https://reference.wolfram.com/language/ref/IndependentVertexSetQ.html (updated 2014).
Wolfram Language. 2010. "IndependentVertexSetQ." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2014. https://reference.wolfram.com/language/ref/IndependentVertexSetQ.html.
Wolfram Language. (2010). IndependentVertexSetQ. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/IndependentVertexSetQ.html