GraphInvariants

function clique_number(g::AbstractGraph)

Return the clique number of g.

Implementation Notes

Computes the independence number of the complement of g.

Example

julia> using Graphs

julia> g = path_graph(5)
{5, 4} undirected simple Int64 graph

julia> clique_number(g)
2

function independence_number(
    g::AbstractGraph{T};
    optimizer=Cbc.Optimizer,
) where T <: Integer

Return the independence number of g.

Implementation Notes

This function relies on max_independent_set to obtain a maximum independent set of g. The optimizer is passed to max_independent_set.

Example

julia> using Graphs

julia> g = cycle_graph(5)
{5, 5} undirected simple Int64 graph

julia> independence_number(g)
2

function max_independent_set(
    g::AbstractGraph{T};
    optimizer=Cbc.Optimizer,
) where T <: Integer

Obtain a maximum independent set of g.

Implementation Notes

The independent set is found by solving the following linear program:

\[\begin{align*} \max_{i \in \mathbb{Z}} & \sum\limits_{v \in V} x_v \\ \;\;\text{s.t.}\; & x_v \in \{0, 1\} & \forall v \in V \\ & x_u + x_v \leq 1 & \forall uv \in E \end{align*}\]

The default optimizer is Cbc as provided by Cbc.jl. You may provide a different optimizer by passing an optimizer constructer (such Cbc.Optimizer or ()->Cbc.Optimizer()) to the optimizer parameter.

Example

julia> using Graphs

julia> g = path_graph(5)
{5, 4} undirected simple Int64 graph

julia> max_independent_set(g)
3-element Vector{Int64}:
 1
 3
 5