# independent set

(redirected from Coclique)

## independent set

[‚in·di‚pen·dənt ′set]
(mathematics)
A set of vertices in a simple graph such that no two vertices in this set are adjacent. Also known as internally stable set.
References in periodicals archive ?
n], and by a coclique a graph with no edges, [[bar.
Since both these graphs can be seen as a graph K2 where each vertex has been substituted by a clique or a coclique, it seems natural to consider graphs constructed from a fixed graph by replacing vertices by cliques or cocliques.
Furthermore, if G satisfies these conditions then so does any graph obtained from G by replacing a vertex of A [union] B [union] {i, j} by a coclique of twin vertices, or a vertex of C [union] {i, j} by a clique of twin vertices.
2] satisfies the conditions of the theorem (it is the simplest case A = B = C = 0), we recover complete graphs, complete bipartite graphs, and the join of a clique and a coclique.
i) G[A] and G[B] are cocliques, and G[C [union] {i, j}] is a clique (inparticular, i j [member of] E);
1] * [zeta])(G) is the number of cocliques in G, and - ([[xi].

Site: Follow: Share:
Open / Close