Title: Theory / Unimportant / CS / Fundamental / Graph / Bondy - Murty / 12 Stable sets and Clique
Tags: examplesSwitchExample1 hasSeenConjDef récupéré

Name: A stable set
Definition: a set of vertices pairwise not adjacent
Page: 295, 296
Chapter: 12
Section: 1
Variables: \(G\) a graph
Definition2: \(V\setminus C\) for \(C\) a covering of \(G\)
Definition3: A clique of \(\bar G\)
Name2: An independent set

Name: A maximum stable set
Definition: A stable set maximal for cardinality
Page: 295
Chapter: 12
Section: 1
Variables: \(G\) a graph

Name: A maximal stable set
Definition: A stable set maximal for inclusion
Page: 295
Chapter: 12
Section: 1
Variables: \(G\) a graph

Name: The stability number of \(G\)
Definition: The cardinality of the maximum stable sets of \(G\)
Page: 296
Chapter: 12
Section: 1
Variables: \(G\) a graph
Notation: \(\alpha(G)\)

Name: An edge covering of \(G\)
Definition: A set of edges adjacent to each vertices
Page: 296
Chapter: 12
Section: 1
Variables: \(G\) a graph
Definition2: \(V(G)\setminus S\) for \(S\) a stable set

Name: The covering number of \(G\)
Definition: The cardinality of the minimum covering of \(G\)
Page: 296
Chapter: 12
Section: 1
Variables: \(G\) a graph
Notation: \(\beta(G)\)

Question: \(\alpha(G)+\beta(G)\)
Answer: equals \(v(G)\)
Page: 296
Chapter: 12
Section: 1
Variables: \(G\) a graph

Name: A clique of \(G\)
Definition: A subset of \(V(G)\) such that each edges are pairwise adjacent
Page: 296
Chapter: 12
Section: 1
Variables: \(G\) a graph
Definition2: A stable set of \(\bar G\)

Name: The clique number of \(G\)
Definition: The size of the maximal clique of \(G\)
Page: 296
Chapter: 12
Section: 1
Variables: \(G\) a graph
Notation: \(\omega(G)\)

Question: \(\omega(\bar G)\)
Answer: equals \(\alpha(G)\)
Page: 296
Chapter: 12
Section: 1
Variables: \(G\) a graph

Question: \(\alpha(\bar G)\)
Answer: equals \(\omega(G)\)
Page: 296
Chapter: 12
Section: 1
Variables: \(G\) a graph