Decomposable graphs and definitions with no quantifier alternation

Let D(G)D(G) be the minimum quantifier depth of a first order sentence ΦΦ that defines a graph GG up to isomorphism. Let D0(G)D0(G) be the version of D(G)D(G) where we do not allow quantifier alternations in ΦΦ. Define q0(n)q0(n) to be the minimum of D0(G)D0(G) over all graphs GG of order nn.We prove that for all nn we have log∗n−log∗log∗n−2≤q0(n)≤log∗n+22,log∗n−log∗log∗n−2≤q0(n)≤log∗n+22, where log∗nlog∗n is equal to the minimum number of iterations of the binary logarithm needed to bring nn to 1 or below. The upper bound is obtained by constructing special graphs with modular decomposition of very small depth.