A controllable graph is a graph whose walk matrix is invertible (Godsil 2012). For a graph on 
vertices with adjacency matrix 
, the walk matrix is
![W(G)=[1,A1,...,A^(n-1)1],](/images/equations/ControllableGraph/NumberedEquation1.svg) |
where 
is an 
-vector
consisting of all 1's. Equivalently, a graph is controllable iff
the matrix rank of its walk matrix equals the graph's
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 graphs are controllable (Wang and Wang 2024). The numbers of controllable graphs on 
, 2, ... vertices are 1, 0, 0, 0, 0, 8, 92, 2332, 85036,
5578994, ... (OEIS A356669; Farrugia 2016)
(summarized in the following table) and 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 2024).
