Graphs with few cliques

In graph theory, a class of graphs is said to have few cliques if every member of the class has a polynomial number of maximal cliques.[1] Certain generally NP-hard computational problems are solvable in polynomial time on such classes of graphs,[1][2] making graphs with few cliques of interest in computational graph theory, network analysis, and other branches of applied mathematics.[3] Informally, a family of graphs has few cliques if the graphs do not have a large number of large clusters.

Definition

edit

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   be a class of graphs. If for every  -vertex graph   in  , there exists a polynomial   such that   has   maximal cliques, then   is said to be a class of graphs with few cliques.[1]

Examples

edit
  • The Turán graph   has an exponential number of maximal cliques. In particular, this graph has exactly  maximal cliques when  , which is asymptotically greater than any polynomial function.[4]: 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   vertices.[5] So the class of Turán graphs does not have few cliques.
  • A tree   on   vertices has as many maximal cliques as edges, since it contains no triangles by definition. Any tree has exactly   edges,[6]: 578  and therefore that number of maximal cliques. So the class of trees has few cliques.
  • A chordal graph on   vertices has at most   maximal cliques,[7]: 49  so chordal graphs have few cliques.
  • Any planar graph on   vertices has at most   maximal cliques,[8] so the class of planar graphs has few cliques.
  • Any  -vertex graph with boxicity   has   maximal cliques,[9]: 46  so the class of graphs with bounded boxicity has few cliques.
  • Any  -vertex graph with degeneracy   has at most   maximal cliques whenever   and  ,[10] so the class of graphs with bounded degeneracy has few cliques.
  • Let   be an intersection graph of   convex polytopes in  -dimensional Euclidean space whose facets are parallel to   hyperplanes. Then the number of maximal cliques of   is  ,[11]: 274  which is polynomial in   for fixed   and  . Therefore, the class of intersection graphs of convex polytopes in fixed-dimensional Euclidean space with a bounded number of facets has few cliques.

References

edit
  1. ^ a b c Prisner, E. (1995). Graphs with Few Cliques. In Y. Alavi & A. Schwenk (Eds.), Graph theory, combinatorics, and algorithms: proceedings of the Seventh Quadrennial International Conference on the Theory and Applications of Graphs (pp. 945–956). New York, N. Y: Wiley.
  2. ^ Rosgen, B., & Stewart, L. (2007). Complexity results on graphs with few cliques. Discrete Mathematics & Theoretical Computer Science, Vol. 9 no. 1 (Graph and Algorithms), 387. https://doi.org/10.46298/dmtcs.387
  3. ^ Fox, J., Roughgarden, T., Seshadhri, C., Wei, F., & Wein, N. (2020). Finding Cliques in Social Networks: A New Distribution-Free Model. SIAM Journal on Computing, 49(2), 448–464. https://doi.org/10.1137/18M1210459
  4. ^ Graham, R. L., Knuth, D. E., & Patashnik, O. (1994). Concrete mathematics: a foundation for computer science (2nd ed.). Reading, Mass: Addison-Wesley.
  5. ^ Moon, J. W., & Moser, L. (1965). On cliques in graphs. Israel Journal of Mathematics, 3(1), 23–28. https://doi.org/10.1007/BF02760024
  6. ^ Pahl, P. J., & Damrath, R. (2001). Mathematical foundations of computational engineering: a handbook. Berlin ; New York: Springer.
  7. ^ 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
  8. ^ 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
  9. ^ Spinrad, J. P. (2003). Intersection and containment representations. In Efficient graph representations (pp. 31–53). Providence, R.I: American Mathematical Society.
  10. ^ 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
  11. ^ 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