# independent set and independence number

A set of vertices in a graph $G$ is called an independent set^{} if there are no edges between the vertices.

The independence number of a graph $G$, usually denoted by $\alpha (G)$, is the size of a maximal independent set in $G$. $\alpha (G)\ge \nu $ means that there are $\nu $ vertices with no edges between them.

An independent set is sometimes called a stable set or an anticlique.

Title | independent set and independence number |
---|---|

Canonical name | IndependentSetAndIndependenceNumber |

Date of creation | 2013-03-22 14:30:06 |

Last modified on | 2013-03-22 14:30:06 |

Owner | rspuzio (6075) |

Last modified by | rspuzio (6075) |

Numerical id | 6 |

Author | rspuzio (6075) |

Entry type | Definition |

Classification | msc 05C69 |

Synonym | stable set |

Synonym | anticlique |

Related topic | Clique2 |

Defines | independent set |

Defines | independence number |