Almost Controllable Graph

Define the walk matrix of a graph on n vertices with adjacency matrix A as


where 1 is an n-vector consisting of all 1's. A graph with vertex count n for which the matrix rank of its walk matrix equals n-1 is then said to be almost controllable (Wang et al. 2021, Wang and Wang 2024). The numbers of almost controllable simple graphs on n=1, 2, ... vertices are 0, 2, 2, 2, 6, 22, 214, 3100, 86578, 3712582, ... (OEIS A371919).


The first few almost controllable graphs are illustrated above.

See also

Controllable Graph

Explore with Wolfram|Alpha


Du, Z.; Liu, F.; Liu, S.; and Qin, Z. "Graphs With n-1 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.

Cite this as:

Weisstein, Eric W. "Almost Controllable Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications