Cliqueful graphs as a means of calculating the maximal number of maximum cliques of simple graphs

07/26/2023

∙

by   Daniel Pfeifer, et al.

∙

0

∙

share

A simple graph on n vertices may contain a lot of maximum cliques. But how many can it potentially contain? We will show that the maximum number of maximum cliques is taken over so-called cliqueful graphs, more specifically, later we will show that it is taken over saturated composite cliqueful graphs, if n ≥ 15. Using this we will show that the graph that contains 3^⌊ n/3 ⌋c maxcliques has the most number of maxcliques on n vertices, where c∈{1,4/3,2}, depending on n mod 3.