  We say that a first order sentence A defines a graph G if A is true on G but
false on any graph non-isomorphic to G. Let L(G) (resp. D(G)) denote the
minimum length (resp. quantifier rank) of a such sentence. We define the
succinctness function s(n) (resp. its variant q(n)) to be the minimum L(G)
(resp. D(G)) over all graphs on n vertices.
  We prove that s(n) and q(n) may be so small that for no general recursive
function f we can have f(s(n))\ge n for all n. However, for the function
q^*(n)=\max_{i\le n}q(i), which is the least monotone nondecreasing function
bounding q(n) from above, we have q^*(n)=(1+o(1))\log^*n, where \log^*n equals
the minimum number of iterations of the binary logarithm sufficient to lower n
below 1.
  We show an upper bound q(n)<\log^*n+5 even under the restriction of the class
of graphs to trees. Under this restriction, for q(n) we also have a matching
lower bound.
  We show a relationship D(G)\ge(1-o(1))\log^*L(G) and prove, using the upper
bound for q(n), that this relationship is tight.
  For a non-negative integer a, let D_a(G) and q_a(n) denote the analogs of
D(G) and q(n) for defining formulas in the negation normal form with at most a
quantifier alternations in any sequence of nested quantifiers. We show a
superrecursive gap between D_0(G) and D_3(G) and hence between D_0(G) and D(G).
Despite it, for q_0(n) we still have a kind of log-star upper bound:
q_0(n)\le2\log^*n+O(1) for infinitely many n.
