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.
McGraw-Hill Dictionary of Scientific & Technical Terms, 6E, Copyright © 2003 by The McGraw-Hill Companies, Inc.
References in periodicals archive ?
It is not very difficult to adapt his proof to show the property holds for complete bipartite graphs and for graphs that are the join of a clique and a coclique. (By a clique we mean a complete graph, [K.sub.n], and by a coclique a graph with no edges, [[bar.K].sub.n]; the join G + H of two graphs G and H is formed by taking their disjoint union and adding an edge between each vertex of G and each vertex of H.) Our main result (Theorem 1 below) generalizes these examples by giving sufficient conditions for a graph to have this property; moreover, it describes graphs for which the property still holds when each vertex is replaced by an arbitrary clique or coclique of twin vertices.
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.
Since [K.sub.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. If we take G = [K.sub.3], we have A = B = 0 and [absolute value of C] = 1.
Thus if [c.sub.k] = 1 in G(c; n) (a clique) the vertex k must be adjacent to both i and j, whereas if [c.sub.k] = 0 (a coclique) then the vertex k must be adjacent to exactly one of i, j.
(i) G[A] and G[B] are cocliques, and G[C [union] {i, j}] is a clique (inparticular, i j [member of] E);
Define a k-near-coloring to be a function f : V [right arrow] [0, k], not necessarily surjective, such that each of the color classes [V.sub.1] = [f.sup.-1](1), ..., [V.sub.k] = [f.sup.-1](k), but not necessarily [V.sub.0] = [f.sup.- 1](0), is a coclique. Then
([[xi].sub.c] * [zeta])(G)= [summation over (cocliques Q] [c.sup.n-[absolute value of Q]].
In particular, ([[xi].sub.1] * [zeta])(G) is the number of cocliques in G, and - ([[xi].sub.-1] x [zeta])(G) is the reduced Euler characteristic of its clique complex.