Clique Graph

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

{{reflist

External links

Information System on Graph Classes and their Inclusions

Graph operations