The reachability problem for graphs cannot be described, in the
sense of descriptive complexity theory, using a single first-order
formula. This is true both for directed and undirected graphs, both
in the finite and infinite. However, if we restrict ourselves to
graphs in which a certain graph parameter is fixed to a certain
value, first-order formulas often suffice. A trivial example are
graphs whose number of vertices is fixed to $n$. In such graphs
reachability can be described using a first-order formula with a
quantifier nesting depth of $\log_2 n$, which is both a lower and an
upper bound. In this paper we investigate how the descriptive
complexity of the reachability problem varies as a function of graph
parameters such as the size of the graph, the clique number, the
matching number, the independence number or the domination
number. The independence number turns out to be the by far most
challenging graph parameter.