Graphs with few cliques

A clique of a graph is a complete subgraph, while a maximal clique is a clique that is not properly contained in another clique. One can regard a clique as a cluster of vertices, since they are by definition all connected to each other by an edge. The concept of clusters is ubiquitous in data analysis, such as on the analysis of social networks. For that reason, limiting the number of possible maximal cliques has computational ramifications for algorithms on graphs or networks.

Formally, let $X$ be a class of graphs. If for every $n$-vertex graph $G$ in $X$, there exists a polynomial $f(n)$ such that $G$

has $O(f(n))$ maximal cliques, then $X$ is said to be a class of graphs with few cliques.

• The Turán graph $T(n,\; \backslash lceil\; n/3\; \backslash rceil)$ has an exponential number of maximal cliques. In particular, this graph has exactly $3^\{n/3\}$maximal cliques when $n\; \backslash equiv\; 0\; \backslash mod\; 3$, which is asymptotically greater than any polynomial function.Graham, R. L., Knuth, D. E., & Patashnik, O. (1994). [https://www.worldcat.org/title/29357079 Concrete mathematics: a foundation for computer science] (2nd ed.). Reading, Mass: Addison-Wesley.{{rp|441}} This graph is sometimes called the Moon-Moser graph, after Moon & Moser showed in 1965 that this graph has the largest number of maximal cliques among all graphs on $n$

vertices.Moon, J. W., & Moser, L. (1965). On cliques in graphs. Israel Journal of Mathematics, 3(1), 23–28. https://doi.org/10.1007/BF02760024 So the class of Turán graphs does not have few cliques.

• A tree $T$

on $n$

vertices has as many maximal cliques as edges, since it contains no triangles by definition. Any tree has exactly $n-1$

edges,Pahl, P. J., & Damrath, R. (2001). [https://www.worldcat.org/title/47208580 Mathematical foundations of computational engineering: a handbook]. Berlin ; New York: Springer.{{rp|578}} and therefore that number of maximal cliques. So the class of trees has few cliques.

• A chordal graph on $n$

vertices has at most $n$

maximal cliques,Gavril, F. (1974). The intersection graphs of subtrees in trees are exactly the chordal graphs. Journal of Combinatorial Theory, Series B, 16(1), 47–56. https://doi.org/10.1016/0095-8956(74)90094-X{{rp|49}} so chordal graphs have few cliques.

• Any planar graph on $n$

vertices has at most $8n-16$

maximal cliques,Wood, D. R. (2007). On the Maximum Number of Cliques in a Graph. Graphs and Combinatorics, 23(3), 337–352. https://doi.org/10.1007/s00373-007-0738-8 so the class of planar graphs has few cliques.

• Any $n$

-vertex graph with boxicity $b$

has $O(n^b)$

maximal cliques,Spinrad, J. P. (2003). Intersection and containment representations. In [https://www.worldcat.org/title/51848305 Efficient graph representations] (pp. 31–53). Providence, R.I: American Mathematical Society.{{rp|46}} so the class of graphs with bounded boxicity has few cliques.

• Any $n$

-vertex graph with degeneracy $d$

has at most $(n-d)3^\{d/3\}$

maximal cliques whenever $d\; \backslash equiv\; 0\; \backslash mod\; 3$

and $n\; \backslash geq\; d+3$

,Eppstein, D., Löffler, M., & Strash, D. (2010). Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time. In O. Cheong, K.-Y. Chwa, & K. Park (Eds.), Algorithms and Computation (Vol. 6506, pp. 403–414). Berlin, Heidelberg: Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-17517-6_36 so the class of graphs with bounded degeneracy has few cliques.

• Let $G$

be an intersection graph of $n$

convex polytopes in $d$

-dimensional Euclidean space whose facets are parallel to $k$

hyperplanes. Then the number of maximal cliques of $G$

is $O\backslash left(n^\{dk^\{d+1\}\}\; \backslash right)$

,Brimkov, V. E., Junosza-Szaniawski, K., Kafer, S., Kratochvíl, J., Pergel, M., Rzążewski, P., et al. (2018). Homothetic polygons and beyond: Maximal cliques in intersection graphs. Discrete Applied Mathematics, 247, 263–277. https://doi.org/10.1016/j.dam.2018.03.046{{rp|274}} which is polynomial in $n$

for fixed $d$

and $k$

. Therefore, the class of intersection graphs of convex polytopes in fixed-dimensional Euclidean space with a bounded number of facets has few cliques.

Category:Graphs

Category:Discrete mathematics