| Independent Sets, Cliques, etc.
-
A set of vertices is called independent
if no two vertices in the set are adjacent.
-
A set of vertices is called a clique
if every pair of vertices in the set is adjacent.
-
An independent set (resp. a clique) is called maximal
if no other independent set (resp. clique) contains it.
-
An independent set (resp. a clique) is called maximum
if its cardinality is maximal among all independent sets (resp. clique) in the graph.
-
(resp.
)
denotes the maximum size of an independent set (resp. a clique) in a graph .
-
A set of edges in a graph is called a matching
if no two of them are incident to the same vertex.
denotes the maximum size of a matching in a graph .
|
|