Clique graph

This article is about a graph whose vertices correspond to maximal cliques in another graph. For other uses, see Clique graph (disambiguation).
A graph G and its clique graph K(G).

In graph theory, a clique graph of an undirected graph G is another graph K(G) that represents the structure of cliques in G.

Clique graphs were discussed at least as early as 1968,[1] and a characterization of clique graphs was given in 1971.[2]

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.[3]

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.[2]

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.[2]

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.[2]

However, this characterization does not lead to efficient algorithms: the problem of recognizing whether a given graph is a clique graph is NP-complete.[4]

References

  1. ^ Hamelink, Ronald C. (1968). "A partial characterization of clique graphs". Journal of Combinatorial Theory. 5 (2): 192–197. doi:10.1016/S0021-9800(68)80055-9.
  2. ^ a b c d Roberts, Fred S.; Spencer, Joel H. (1971). "A characterization of clique graphs". Journal of Combinatorial Theory. Series B. 10 (2): 102–108. doi:10.1016/0095-8956(71)90070-0.
  3. ^ Szwarcfiter, Jayme L.; Bornstein, Claudson F. (1994). "Clique graphs of chordal and path graphs". SIAM Journal on Discrete Mathematics. 7 (2): 331–336. CiteSeerX 10.1.1.52.521. doi:10.1137/S0895480191223191.
  4. ^ Alcón, Liliana; Faria, Luerbio; de Figueiredo, Celina M. H.; Gutierrez, Marisa (2009). "The complexity of clique graph recognition". Theoretical Computer Science. 410 (21–23): 2072–2083. doi:10.1016/j.tcs.2009.01.018. MR 2519298.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.