IndependentVertexSetQ
IndependentVertexSetQ[g,vlist]
yields True if the vertex list vlist is an independent vertex set in the graph g, and False otherwise.
Details
- 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.
Examples
open all close allBasic Examples (2)
Scope (5)
IndependentVertexSetQ[[image], {2, 3, 4}]IndependentVertexSetQ[[image], {2, 3, 4}]IndependentVertexSetQ[[image], {2, 3, 4}]IndependentVertexSetQ[[image], {2, 3, 4}]IndependentVertexSetQ works with large graphs:
g = GridGraph[{10, 10, 10, 10}];IndependentVertexSetQ[g, {1, 2}]//TimingApplications (2)
Enumerate all independent vertex sets for a cycle graph:
g = CycleGraph[4, VertexSize -> Small]Enumerate all subsets of vertices and select the ones that are independent vertex sets:
Subsets[VertexList[g]]vcl = Select[%, IndependentVertexSetQ[g, #]&]Highlight independent vertex sets:
Table[HighlightGraph[g, h], {h, vcl}]Enumerate all maximum independent vertex sets for a Petersen graph:
g = PetersenGraph[5, 2, VertexSize -> Medium]Find the size of a maximum independent vertex set:
FindIndependentVertexSet[g]n = Length[%]Enumerate all maximum independent vertex sets:
vsl = Select[Subsets[VertexList[g], {4}], IndependentVertexSetQ[g, #]&]Highlight maximum independent sets:
Table[HighlightGraph[g, h], {h, vsl}]Properties & Relations (4)
A largest independent vertex set can be found using FindIndependentVertexSet:
PetersenGraph[5, 2]IndependentVertexSetQ[%, First[FindIndependentVertexSet[%]]]The complement of an independent vertex set is a vertex cover:
g = GridGraph[{2, 3}]Complement[VertexList[%], First[FindIndependentVertexSet[%]]]VertexCoverQ[g, %]The complement subgraph given by an independent vertex set is complete:
g = PetersenGraph[5, 2]Subgraph[GraphComplement[g], FindIndependentVertexSet[g]]CompleteGraphQ[%]Bipartite graphs have equal-length edge covers and independent vertex sets:
g = CompleteGraph[{2, 3}]Length[First[FindIndependentVertexSet[g]]] == Length[FindEdgeCover[g]]Text
Wolfram Research (2010), IndependentVertexSetQ, Wolfram Language function, https://reference.wolfram.com/language/ref/IndependentVertexSetQ.html (updated 2014).
CMS
Wolfram Language. 2010. "IndependentVertexSetQ." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2014. https://reference.wolfram.com/language/ref/IndependentVertexSetQ.html.
APA
Wolfram Language. (2010). IndependentVertexSetQ. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/IndependentVertexSetQ.html