Clique graph

Last updated

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

Contents

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

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]

Related Research Articles

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

<span class="mw-page-title-main">Clique problem</span> Task of computing complete subgraphs

In computer science, the clique problem is the computational problem of finding cliques in a graph. It has several different formulations depending on which cliques, and what information about the cliques, should be found. Common formulations of the clique problem include finding a maximum clique, finding a maximum weight clique in a weighted graph, listing all maximal cliques, and solving the decision problem of testing whether a graph contains a clique larger than a given size.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

<span class="mw-page-title-main">Clique (graph theory)</span> Adjacent subset of an undirected graph

In the mathematical area of graph theory, a clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph is an induced subgraph of that is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied.

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. L(G) is constructed in the following way: for each edge in G, make a vertex in L(G); for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L(G).

<span class="mw-page-title-main">Erdős–Faber–Lovász conjecture</span>

In graph theory, the Erdős–Faber–Lovász conjecture is a problem about graph coloring, named after Paul Erdős, Vance Faber, and László Lovász, who formulated it in 1972. It says:

<span class="mw-page-title-main">Chordal graph</span> Graph where all long cycles have a chord

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs or triangulated graphs: a chordal completion of a graph is typically called a triangulation of that graph.

<span class="mw-page-title-main">Cograph</span> Graph formed by complementation and disjoint union

In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K1 and is closed under complementation and disjoint union.

In graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph, and the pathwidth of G is a number that measures how much the path was thickened to form G. More formally, a path-decomposition is a sequence of subsets of vertices of G such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as interval thickness, vertex separation number, or node searching number.

<span class="mw-page-title-main">Intersection graph</span> Graph representing intersections between given sets

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 of sets that are used to form an intersection representation of them.

<span class="mw-page-title-main">Median graph</span> Graph with a median for each three vertices

In graph theory, a division of mathematics, a median graph is an undirected graph in which every three vertices a, b, and c have a unique median: a vertex m(a,b,c) that belongs to shortest paths between each pair of a, b, and c.

<span class="mw-page-title-main">Clique-sum</span> Gluing graphs at complete subgraphs

In graph theory, a branch of mathematics, a clique sum is a way of combining two graphs by gluing them together at a clique, analogous to the connected sum operation in topology. If two graphs G and H each contain cliques of equal size, the clique-sum of G and H is formed from their disjoint union by identifying pairs of vertices in these two cliques to form a single shared clique, and then deleting all the clique edges or possibly deleting some of the clique edges. A k-clique-sum is a clique-sum in which both cliques have exactly k vertices. One may also form clique-sums and k-clique-sums of more than two graphs, by repeated application of the clique-sum operation.

<span class="mw-page-title-main">Clique complex</span> Abstract simplicial complex describing a graphs cliques

Clique complexes, independence complexes, flag complexes, Whitney complexes and conformal hypergraphs are closely related mathematical objects in graph theory and geometric topology that each describe the cliques of an undirected graph.

<span class="mw-page-title-main">Pancyclic graph</span>

In the mathematical study of graph theory, a pancyclic graph is a directed graph or undirected graph that contains cycles of all possible lengths from three up to the number of vertices in the graph. Pancyclic graphs are a generalization of Hamiltonian graphs, graphs which have a cycle of the maximum possible length.

<span class="mw-page-title-main">Block graph</span> Graph whose biconnected components are all cliques

In graph theory, a branch of combinatorial mathematics, a block graph or clique tree is a type of undirected graph in which every biconnected component (block) is a clique.

In the mathematical field of graph theory, the intersection number of a graph is the smallest number of elements in a representation of as an intersection graph of finite sets. In such a representation, each vertex is represented as a set, and two vertices are connected by an edge whenever their sets have a common element. Equivalently, the intersection number is the smallest number of cliques needed to cover all of the edges of .

<span class="mw-page-title-main">Well-covered graph</span> Graph with equal-size maximal independent sets

In graph theory, a well-covered graph is an undirected graph in which the minimal vertex covers all have the same size. Here, a vertex cover is a set of vertices that touches all edges, and it is minimal if removing any vertex from it would leave some edge uncovered. Equivalently, well-covered graphs are the graphs in which all maximal independent sets have equal size. Well-covered graphs were defined and first studied by Michael D. Plummer in 1970.

<span class="mw-page-title-main">Ptolemaic graph</span>

In graph theory, a Ptolemaic graph is an undirected graph whose shortest path distances obey Ptolemy's inequality, which in turn was named after the Greek astronomer and mathematician Ptolemy. The Ptolemaic graphs are exactly the graphs that are both chordal and distance-hereditary; they include the block graphs and are a subclass of the perfect graphs.

In graph theory, a geodetic graph is an undirected graph such that there exists a unique (unweighted) shortest path between each two vertices.

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. 1 2 3 4 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.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.