TOPICS
Define the walk matrix of a graph on 
vertices with adjacency matrix 
as
![W(G)=[1,A1,...,A^(n-1)1],](/images/equations/AlmostControllableGraph/NumberedEquation1.svg) |
where 
is an 
-vector
consisting of all 1's. A graph with vertex count 
for which the matrix rank of
its walk matrix equals 
is then said to be almost controllable (Wang et al. 2021,
Wang and Wang 2024). The numbers of almost controllable simple graphs on 
, 2, ... vertices are 0, 2, 2, 2, 6, 22, 214, 3100, 86578,
3712582, ... (OEIS A371919).
The first few almost controllable graphs are illustrated above.
Main Eigenvalues." Disc. Math. 344, 112397, 2021.Du,
Z.; You, L.; Liu, H.; and Liu, F. "Further Results on Almost Controllable Graphs."
Linear Algebra Appl. 677, 31-50, 2023.Du, Z., You, L.,
and Liu, H. "Almost Controllable Graphs and Beyond." Disc. Math. 347,
113743, 2024.Liu, F. and Siemons, J. "Unlocking the Walk Matrix
of a Graph." J. Algebraic Combin. 55, 663-69, 2022.Qiu,
L.; Wang, W.; Wang, W.; and Zhang, H. "A New Criterion for Almost Controllable
Graphs Being Determined by Their Generalized Spectra." Disc. Math. 345,
113060, 2022.Sloane, N. J. A. Sequence A371919
in "The On-Line Encyclopedia of Integer Sequences."Wang, W.
and Wang, W. "Haemers' Conjecture: An Algorithmic Perspective." Experimental
Math., 10 Apr 2024.Wang, W.; Liu, F.; and Wang, W. "Generalized
Spectral Characterizations of Almost Controllable Graphs." Europ. J. Combin. 96,
103348, 2021.
Weisstein, Eric W. "Almost Controllable Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/AlmostControllableGraph.html
