next | previous | forward | backward | up | index | toc

# independenceNumber -- determines the independence number of a graph

## Synopsis

• Usage:
d = independenceNumber G
• Inputs:
• G, ,
• Outputs:
• d, an integer, the independence number of G

## Description

This function returns the maximum number of independent vertices in a graph. This number can be found by computing the dimension of the simplicial complex whose faces are the independent sets (see independenceComplex) and adding 1 to this number.

 i1 : R = QQ[a..e]; i2 : c4 = graph {a*b,b*c,c*d,d*a} -- 4-cycle plus an isolated vertex!!!! o2 = Graph{"edges" => {{a, b}, {b, c}, {a, d}, {c, d}}} "ring" => R "vertices" => {a, b, c, d, e} o2 : Graph i3 : c5 = graph {a*b,b*c,c*d,d*e,e*a} -- 5-cycle o3 = Graph{"edges" => {{a, b}, {b, c}, {c, d}, {a, e}, {d, e}}} "ring" => R "vertices" => {a, b, c, d, e} o3 : Graph i4 : independenceNumber c4 o4 = 3 i5 : independenceNumber c5 o5 = 2 i6 : dim independenceComplex c4 + 1 == independenceNumber c4 o6 = true