independenceNumber -- determines the independence number of a graph

Synopsis

Usage:
d = independenceNumber G
Inputs:
- G, a graph
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

Ways to use `independenceNumber` :

independenceNumber(Graph)

independenceNumber -- determines the independence number of a graph

Synopsis

Description

See also

Ways to use independenceNumber :

Ways to use `independenceNumber` :