O'Rourke and Touri (2016) proved that almost all graphs are controllable (Wang and Wang 2025). 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).
Farrugia, A. "On Strongly Asymmetric and Controllable Primitive Graphs." Disc. Appl. Math.211, 58-67, 2016.Godsil,
C. "Controllable Subsets in Graphs." Ann. Comb.16, 733-744,
2012.O'Rourke, S. and Touri, B. "On a Conjecture of Godsil concerning
Controllable Random Graphs." SIAM J. Control Optim.54, 3347-3378,
2016.Sloane, N. J. A. Sequences A356669
and A371897 in "The On-Line Encyclopedia
of Integer Sequences."Wang, W.; Liu, F.; and Wang, W. "Generalized
Spectral Characterizations of Almost Controllable Graphs." Europ. J. Combin.96,
103348, 2021.Wang, W. and Wang, W. "Haemers' Conjecture: An Algorithmic
Perspective." Experimental Math.34, 147-161, 2025. https://doi.org/10.1080/10586458.2024.2337229.Yoon,
M.-G.; Rowlinson, P.; Cvetković, D.; and Stanić, Z. "Controllability
of Multi-Agent Dynamical Systems with a Broadcasting Control Signal." Asian
J. Control16, 1066-1072, 2014.
.
, 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).
for which the matrix
rank of its walk matrix equals 
is said to be almost
controllable (Wang et al. 2021, Wang and Wang 2025).
