A bijection between cliques in graphs and factorizations in free monoids

AbstractIf A∗ is the free monoid over the alphabet A, the maximal number ϕ(n) of factorizations of a word of length n in some submonoid of A∗ is such that ϕ(3m)=2×3m−1, ϕ(3m>+1)=3m and ϕ(3m+2)=4×3m−1.We also prove that the maximal number ψ(n) of cyclic interpretations in a submonoid C∗ of a word w of length n and the maximal number ξ(n) of prefix interpretations in C∗ of w are equal to ϕ(n+1).Moon and Moser (1965) have proved directly that the maximal number of cliques in a graph having n vertices is also equal to ϕ(n+1).We give here a new proof of this result by using a bijection from the set of prefix interpretations of a word into the set of cliques in an associated graph. By the same bijection we determine all the graphs having a maximal number of cliques.Moreover, we obtain two new NP-complete problems by using the same bijection