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 set 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:

Introduced in 2010
 (8.0)
 |
Updated in 2014
 (10.0)