Clique graph

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In graph theory, a clique graph of an undirected graph is another graph that represents the structure of cliques in . Clique graphs were discussed at least as early as 1968, and a characterization of clique graphs was given in 1971.

In graph theory, a clique graph of an undirected graph is another graph that represents the structure of cliques in . Clique graphs were discussed at least as early as 1968, and a characterization of clique graphs was given in 1971.

Formal definition

A clique of a graph G is a set X of vertices of G with the property that every pair of distinct vertices in X are adjacent in G. A maximal clique of a graph G is a clique X of vertices of G, such that there is no clique Y of vertices of G that contains all of X and at least one other vertex. Given a graph G, its clique graph K(G) is a graph such that every vertex of K(G) represents a maximal clique of G; and two vertices of K(G) are adjacent when the underlying cliques in G share at least one vertex in common. That is, the clique graph K(G) is the intersection graph of the maximal cliques of G.

Characterization

A graph H is the clique graph K(G) of another graph if and only if there exists a collection C of cliques in H whose union covers all the edges of H, such that C forms a Helly family. This means that, if S is a subset of C with the property that every two members of S have a non-empty intersection, then S itself should also have a non-empty intersection. However, the cliques in C do not necessarily have to be maximal cliques. When H =K(G), a family C of this type may be constructed in which each clique in C corresponds to a vertex v in G, and consists of the cliques in G that contain v. These cliques all have v in their intersection, so they form a clique in H. The family C constructed in this way has the Helly property, because any subfamily of C with pairwise nonempty intersections must correspond to a clique in G, which can be extended to a maximal clique that belongs to the intersection of the subfamily. Conversely, when H has a Helly family C of its cliques, covering all edges of H, then it is the clique graph K(G) for a graph G whose vertices are the disjoint union of the vertices of H and the elements of C. This graph G has an edge for each pair of cliques in C with nonempty intersection, and for each pair of a vertex of H and a clique in C that contains it. However, it does not contain any edges connecting pairs of vertices in H. The maximal cliques in this graph G each consist of one vertex of H together with all the cliques in C that contain it, and their intersection graph is isomorphic to H. However, this characterization does not lead to efficient algorithms: the problem of recognizing whether a given graph is a clique graph is NP-complete.

References

External links

Information System on Graph Classes and their Inclusions: clique graph

Text derived from https://en.wikipedia.org/w/index.php?oldid=1369271113 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001369271113 · captured 1786657551.0 · version history

Cite this page as: encyclopegia.org, “Clique graph”, snapshot enwiki-001369271113. https://encyclopegia.org/a/clique-graph

Sources cited in this revision

1 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.