A controllable graph is a finite simple graph on 
vertices whose walk matrix
is nonsingular (Godsil 2012). Equivalently,
a graph is controllable iff the
matrix rank of its walk
matrix equals its vertex count 
.
Controllable graphs are identity graphs (Godsil 2012).
A graph is controllable iff its graph complement is (Godsil 2012).
O'Rourke and Touri (2016) proved that almost all labeled simple graphs are controllable. The numbers of controllable graphs,
counted up to graph isomorphism, on 
, 2, ... vertices are 1,
0, 0, 0, 0, 8, 92, 2332, 85036, 5578994, ... (OEIS A356669;
Farrugia 2016), as summarized in the following table. The corresponding numbers of
connected controllable graphs
are 1, 0, 0, 0, 0, 8, 85, 2275, 83034, 5512362, ... (OEIS A371897).
 | # controllable | # graphs | fraction |
| OEIS | A356669 | A000088 | |
| 1 | 1 | 1 | 100% |
| 2 | 0 | 2 | 0% |
| 3 | 0 | 4 | 0% |
| 4 | 0 | 11 | 0% |
| 5 | 0 | 34 | 0% |
| 6 | 8 | 156 | 5.13% |
| 7 | 92 | 1044 | 8.81% |
| 8 | 2332 | 12346 | 18.9% |
| 9 | 85036 | 274668 | 31.0% |
| 10 | 5578994 | 12005168 | 46.5% |
The eight controllable graphs on 6 vertices are illustrated above.
A graph with vertex count 
for which the matrix
rank of its walk matrix equals 
is said to be almost
controllable (Wang et al. 2021, Wang and Wang 2025).
