Strongly uncontrollable network topologies

I. INTRODUCTION

• Equitable partitions can create invariant subspaces that obstruct controllability when control nodes preserve those subspaces; the paper studies this obstruction under a common broadcast signal.Minimal controllability asks for the fewest control nodes, and heuristic approximate solutions are known for generic systems.Source: §I · p. 1
• Strongly uncontrollable graphs have distinct Laplacian eigenvalues yet remain uncontrollable for every binary input vector; the numerical search found none for n ≤ 7.The paper reports enumerations for 8 ≤ n ≤ 12; for adjacency matrices, it found none through n = 10 and conjectures none exist.Source: §I · p. 1, Table I · p. 1
• Twin nodes together with certain equitable partitions characterize strong uncontrollability, and related vertex additions can preserve the property.The characterized topologies also require control of approximately half their nodes for any chance of controllability.Source: §I · pp. 1–2

II. PRELIMINARIES

• The section introduces notation used in the paper.Source: §II · p. 2
• It reviews equitable partitions and their role in network controllability.Source: §II · p. 2
• The section also presents technical results.Source: §II · p. 2

A. Notation

• The section defines simple spectrum, matrix range, orthogonal complement, M-invariance, and binary-vector notation.It also specifies the all-ones vector, standard basis vectors, and N0.Source: A. Notation · p. 2
• For a simple graph, the Laplacian is L(G) = D − A, with D the degree matrix and A the adjacency matrix.The text also defines weighted digraphs, neighborhoods, and vertex degrees.Source: A. Notation · p. 2
• A linear single-input system is controllable exactly when its input vector and successive A-images span R^n; the PBH test gives an equivalent eigenvector condition.Source: A. Notation · p. 2

B. Almost equitable partitions

• An almost equitable partition (AEP) makes the characteristic-matrix range invariant under the Laplacian, and the quotient Laplacian is obtained by projecting onto that range.The quotient graph represents the cells of the partition as vertices.Source: B. Almost equitable partitions · pp. 2–3
• For a symmetric graph Laplacian, eigenvectors split between vectors constant on each AEP cell and vectors that sum to zero within each cell.An input vector constant on the cells is orthogonal to the latter eigenvectors, making the system uncontrollable by the PBH test.Source: B. Almost equitable partitions · p. 3
• In the 11-vertex example, an input constant on the four AEP cells is uncontrollable because it is orthogonal to every eigenvector in the partition kernel.The cited example uses b = (0,0,0,0,1,1,0,0,0,0,1).Source: B. Almost equitable partitions · p. 3
• A π-regular AEP of the quotient graph restores this eigenvector splitting for the quotient Laplacian, even though that matrix need not be symmetric.The associated condition is that cells grouped together by the quotient partition have equal cardinality.Source: B. Almost equitable partitions · p. 4

III. TWIN GRAPHS

• A twin pair induces a Faria eigenvector eu − ev with Laplacian eigenvalue deg(u) + A(u,v).Twin vertices have identical neighborhoods apart from each other; swapping them is a graph automorphism.Source: §III · p. 4
• With a simple Laplacian spectrum, the maximum number of twin pairs is n/2 − 1 for even n and (n − 1)/2 for odd n.Both bounds are sharp.Source: §III · p. 4
• A twin graph has simple Laplacian spectrum and the maximum number of twins permitted by its vertex count.Numerical enumeration found 12 such graphs on 7 vertices, 36 on 8, 42 on 9, and 924 on 10; existence for every n ≥ 7 is conjectured.Source: §III · p. 5
• A controllable n-vertex twin graph requires at least t controlled nodes, where t is its number of twin pairs.Each twin cell contributes a Faria eigenvector, so leaving a twin cell without an input makes the system uncontrollable.Source: §III · p. 5
• Twin graphs show that simple eigenvalues do not eliminate the need to control a significant fraction of nodes in consensus-type dynamics.An 8-vertex example has three twins, and an 11-vertex example has five, each with simple Laplacian spectrum.Source: §III · pp. 4–5

IV. STRONGLY UNCONTROLLABLE GRAPHS

• A graph is strongly uncontrollable when its Laplacian has simple spectrum and every binary vector b makes (L, b) uncontrollable.Source: §IV · p. 5
• Twin vertices alone are insufficient; quotient AEPs supply additional structure used with Faria eigenvectors and the PBH test to establish uncontrollability for every binary input.The proof handles vectors that select exactly one vertex from each twin cell by showing they are orthogonal to a Laplacian eigenvector.Source: §IV · pp. 5–6
• For even twin graphs, a quotient AEP with the two singleton cells in one part is sufficient for strong uncontrollability; for odd graphs, the condition uses the final singleton vertex.The even and odd conditions are stated separately for the twin partition quotient.Source: §IV · pp. 5–6
• The 11-vertex example satisfies Theorem IV.2, with ρ = {{C1, C5}, {C2, C4}, {C3}, {v11}} forming an AEP of the quotient graph.Source: §IV · p. 6, Figure 3 · p. 6
• Numerical investigations found all strongly uncontrollable graphs through 12 vertices had at least three twin pairs, but the small search supports only a conjecture about adjacency-matrix cases.No strongly uncontrollable signless-Laplacian graphs were found through 10 vertices; the authors suggest the property may be limited to consensus-type dynamics.Source: §IV · p. 7

Theorem V.2: Adding one vertex to all vertices

• Adding one vertex connected to every vertex preserves strong uncontrollability if and only if the original Laplacian’s spectral radius is less than n.In that case, the automorphism groups of the original and enlarged graphs are equal as subgroups of S_{n+1}.Source: §V · p. 7

Example V.1

• Theorem V.2 shows twin structure is not necessary: all ten strongly uncontrollable n=8 graphs induce non-twin strongly uncontrollable n=9 graphs, and s(9)=12.The counts are s(8)=10 and s(9)=12.Source: §V · p. 7

Theorem V.3: Adding two vertices

• Joining two isolated vertices to a strongly uncontrollable graph preserves the property if and only if n−2 and n are not eigenvalues of its Laplacian.The enlarged graph’s automorphism group is generated by the original group and the transposition of the two added vertices.Source: §V · pp. 7–8

Remark V.1: Limit on adding vertices

• The empty-graph joining construction cannot extend to more than two added vertices, because the enlarged graph would have an automorphism of order greater than two and thus lack distinct eigenvalues.Source: §V · p. 8

Theorem V.4: Attaching a vertex to a universal vertex

• Attaching a new vertex only to a degree-(n−1) vertex preserves strong uncontrollability if and only if 1 is not an eigenvalue of the original Laplacian.The original and enlarged graphs have equal automorphism groups as subgroups of S_{n+1}.Source: §V · p. 8

• The characterized topologies are uncontrollable for any subset of control nodes emitting a common signal under Laplacian consensus dynamics.Source: §VI · p. 8
• Their strong uncontrollability is characterized by maximal twin nodes and certain almost equitable partitions, not repeated Laplacian eigenvalues.Source: §VI · p. 8
• The paper provides a sufficient condition for strong uncontrollability and describes network perturbations that preserve the property.Source: §VI · p. 8
• These topologies require control of essentially half the nodes for any chance of controllability.Source: §VI · p. 8

• For a partition π, its characteristic matrix Pπ yields K=Pπ^T Pπ=diag(|C1|,…,|Ck|), and the quotient Laplacian is Lπ=K^-1Pπ^T LPπ.Source: Appendix A · p. 8
• When ρ is a π-regular partition of π, K Pρ=Pρ K̃ and K^-1Pρ=Pρ K̃^-1.Source: Appendix A · p. 8
• The quotient Laplacians satisfy LπPρ=PρLπρ, where πρ is the ρ-merge of π.Source: Appendix A · p. 9