Decomposable graphs and definitions with no quantifier alternation

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