TOPICS
Search

Controllable Graph


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

 W(G)=[1,A1,...,A^(n-1)1],

where 1 is an n-vector consisting of all 1's. Then a graph is said to be controlable if its walk matrix is invertible (Godsil 2012). Equivalently, graph is controllable iff the matrix rank of its walk matrix equals the graph's vertex count n.

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 n=1, 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).

n# controllable# graphsfraction
OEISA356669A00088
111100%
2020%
3040%
40110%
50340%
681565.13%
79210448.81%
823321234618.9%
98503627466831.0%
1055789941200516846.5%
ControllableGraphs

The eight controllable graphs on 6 vertices are illustrated above.

A graph with vertex count n for which the matrix rank of its walk matrix equals n-1 is said to be almost controllable (Wang et al. 2021, Wang and Wang 2024).


See also

Adjacency Matrix, Almost Controllable Graph

Explore with Wolfram|Alpha

References

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. 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.Yoon, M.-G.; Rowlinson, P.; Cvetković, D.; and Stanić, Z. "Controllability of Multi-Agent Dynamical Systems With a Broadcasting Control Signal." Asian J. Control 16, 1066-1072, 2014.

Cite this as:

Weisstein, Eric W. "Controllable Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ControllableGraph.html

Subject classifications