BUILT-IN MATHEMATICA SYMBOL

IndependentVertexSetQ

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.

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

Test for a directed graph:

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

Out[1]=

Out[2]=

Test for a directed graph:

Out[1]=

Out[2]=

Test undirected graphs:

Directed 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 maximal independent vertex sets for a Petersen graph:

Find the size of a maximal independent vertex set:

Enumerate all maximal independent vertex sets:

Highlight maximal independent sets:

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: