Clique (graph theory)

Clique graphs are objects of graph theory. Finding a clique of a given size in a graph is an NP -complete problem and thus also in information technology is a relevant research and application. The term clique goes back on Luce Perry, who used the term first social networks in which a group in which everyone knows everyone else, is referred to as just such.

Definition

Clique graphs are defined for loop-free and undirected graphs. A graph is a clique if all nodes are interconnected in pairs (Complete graph ) and there is no node outside the clique is connected to all nodes of the clique. The clique graph K ( G) of a graph G is the graph that results when all the cliques associated with one node and two nodes are connected if the corresponding cliques in G have common nodes. Iterated clique graphs are defined as follows:

Two directly interconnected nodes represent doing a clique of size 2 dar.

Clique behavior

If you look at graphs of arbitrarily large cliques iteration there are two possible behaviors. Clique periodic behavior occurs when there is a graph corresponding to a graph that has occurred earlier in the sequence of cliques graph. So:

The second possibility is that the graph is clique divergent is. This is the case, when it is no upper bound on the number of nodes that make up an arbitrary graph of the sequence of iterated cliques graph.

V ( G) is the set of nodes of the graph G.

In addition, the case is discriminated that the iterated clique graphs from a given iteration are equal to the Einvertexgraph, a graph consists of exactly one node. In this case, the clique refers to a convergent behavior.

The clique - Helly property

A graph has clique - Helly property, when the family of his cliques has the Helly property. Graphs with clique - Helly property have in connection with clique graphs on some interesting properties.

The clique graph of graphs with clique - Helly property themselves possess the clique - Helly property.

There are to every graph H with the clique - Helly property to a graph G so that the clique graph of G isomorphic to H.

The clique graph of the second iteration of K2 ( G) of a graph G with clique - Helly property is an induced subgraph of G. A graph with clique - Helly property is therefore never clique divergent and its period is at most two.