graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, a clique graph of an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

is another graph that represents the structure of

cliques A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...

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

Formal definition

clique A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...

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. The clique graph ''K''(''G'') can also be characterized as the

intersection graph In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types o ...

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 In combinatorics, a Helly family of order is a family of sets in which every minimal ''subfamily with an empty intersection'' has or fewer sets in it. Equivalently, every finite subfamily such that every -fold intersection is non-empty has non ...

. 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 In mathematics, a disjoint union (or discriminated union) of a family of sets (A_i : i\in I) is a set A, often denoted by \bigsqcup_ A_i, with an injection of each A_i into A, such that the images of these injections form a partition of A (th ...

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 In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...

References

{{reflist

External links

Information System on Graph Classes and their Inclusions
Graph operations