Cliques Graph

The articles clique graph and clique (graph theory) overlap thematically. Help me to better differentiate or merge the articles (→ instructions ) . To do this, take part in the relevant redundancy discussion . Please remove this module only after the redundancy has been completely processed and do not forget to include the relevant entry on the redundancy discussion page{{ Done | 1 = ~~~~}}to mark. Tavin ( discussion ) 5:56 p.m. , Jan. 10, 2018 (CET)

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

definition

Clique graphs are defined for loopless and undirected graphs . A graph is a clique if all nodes are connected in pairs ( complete graph ) and there is no node outside the clique that is connected to all nodes of the clique. The clique graph K (G) of a graph G is the graph that results when all cliques are each assigned to a node and two nodes are connected when the associated cliques in G have common nodes. Iterated clique graphs are defined as follows:

${\ displaystyle K ^ {n} (G) = K (K ^ {n-1} (G)), ~ {\ text {if}} ~ n ~> ~ 0}$

${\ displaystyle K ^ {n} (G) = G, ~ {\ text {if}} ~ n ~ = ~ 0}$

Two nodes that are directly connected to each other represent a clique of size 2.

Clique behavior

When looking at clique graphs of arbitrarily high iteration there are two possible behaviors. Periodic clique behavior occurs when there is a graph that corresponds to a graph that occurred earlier in the sequence of clique graphs. So:

${\ displaystyle K ^ {i} (G) = K ^ {j} (G), ~ i \ neq j}$

The second possibility is that the graph is cliquendivergent . This is the case if there is no upper bound on the number of nodes that make up any graph from the sequence of iterated clique graphs.

${\ displaystyle \ lim _ {i \ to \ infty} | V (K ^ {i} (G)) | = \ infty}$

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

In addition, a distinction is made between the iterated clique graphs from a certain iteration onwards are equal to the one-vertex graph, a graph that consists of exactly one node. In this case, the clique behavior is called convergent .

The Clique Helly property

The Hajos graph. It is the smallest graph that does not have the Clique-Helly property.

A graph has the Clique-Helly property if the family of its cliques has the Helly property . Graphs with the clique-Helly property have some interesting properties in connection with clique graphs.

The clique graphs of graphs with the clique-helly property themselves have the clique-helly property.

For every graph H with the clique-Helly property there is a graph G, so that the clique graph of G is isomorphic to H.

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

literature

JL Szwarcfiter: A Survey on Clique Graphs . In: Recent Advances in Algorithmsand Combinatorics . Springer, New York 2003, pp. 109-136.
F. Escalante: About iterated clique graphs . In: Treatises of the Mathematical Seminar of the University of Hamburg . Volume 39. Springer, Berlin / Heidelberg 1973, pp. 58-68.

Individual evidence

^ R. Duncan Luce, Albert D. Perry: A method of matrix analysis of group structure . In: Psychometrika , 14 (2), 1949, pp. 95-116, doi: 10.1007 / BF02289146 , PMID 18152948 .

[1] R. Duncan Luce, Albert D. Perry: A method of matrix analysis of group structure . In: Psychometrika , 14 (2), 1949, pp. 95-116, doi: 10.1007 / BF02289146 , PMID 18152948 .