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 allclose all

Basic Examples  (2)

Test whether a set of vertices is an independent vertex set:

Not all sets of vertices are independent vertex sets in a graph:

Scope  (5)

Test undirected graphs:

Directed graphs:

Multigraphs:

Mixed graphs:

IndependentVertexSetQ works with large graphs:

Applications  (2)

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:

Highlight maximum independent 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).

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

BibTeX

@misc{reference.wolfram_2024_independentvertexsetq, author="Wolfram Research", title="{IndependentVertexSetQ}", year="2014", howpublished="\url{https://reference.wolfram.com/language/ref/IndependentVertexSetQ.html}", note=[Accessed: 18-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_independentvertexsetq, organization={Wolfram Research}, title={IndependentVertexSetQ}, year={2014}, url={https://reference.wolfram.com/language/ref/IndependentVertexSetQ.html}, note=[Accessed: 18-November-2024 ]}