Cliques Graph
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:
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:
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.
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
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 2 (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 .