Controllable subsets in graphs

DOI10.1007/S00026-012-0156-3MaRDI QIDQ1929751zbMATH OpenOpenAlexFDO

Authors Chris Godsil

Publication date 9 January 2013

Published in Annals of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1010.3231

zbMATH Keywords

adjacency matrixcontrollabilitywalkscontrollable pairs

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Basic linear algebra (15A99) Controllability (93B05)

Abstract: Let $X$ be a graph on $v$ vertices with adjacency matrix $A$, and let let $S$ be a subset of its vertices with characteristic vector $z$. We say that the pair $(X,S)$ is controllable if the vectors $A^{r}z$ for $r=1,ldots,v-1$ span $mathbb{R}^v$. Our concern is chiefly with the cases where $S=V(X)$, or $S$ is a single vertex. In this paper we develop the basic theory of controllable pairs. We will see that if $(X,S)$ is controllable then the only automorphism of $X$ that fixes $S$ as a set is the identity. If $(X,S)$ is controllable for some subset $S$ then the eigenvalues of $A$ are all simple.

Recommendations

• Controllability of certain real symmetric matrices with application to controllability of graphs
• Controllable graphs
• Further results on controllable graphs
• Controllability of NEPSes of graphs
• Controllable graphs with least eigenvalue at least \(-2\)

Cites work

• scientific article; zbMATH DE number 3711820 (Why is no real title available?)
• A note on cospectral graphs
• A sufficient condition for a family of graphs being determined by their generalized spectra

Cited in

(38)

• The Smith normal form of the walk matrix of the Dynkin graph \(D_n\) for \(n \equiv 0 \pmod{4}\)
• On the construction of Q-controllable graphs
• Controllability of certain real symmetric matrices with application to controllability of graphs
• How to suppress dark states in quantum networks and bio-engineered structures
• Eigenvectors and controllability of non-Hermitian random matrices and directed graphs
• A simple arithmetic criterion for graphs being determined by their generalized spectra
• Laplacian controllability classes for threshold graphs
• A new method for constructing graphs determined by their generalized spectrum
• Generalized spectral characterizations of almost controllable graphs
• New families of graphs determined by their generalized spectrum
• An improved condition for a family of trees being determined by their generalized spectrum
• Graphs with \(n - 1\) main eigenvalues
• Unlocking the walk matrix of a graph
• Controllability of networked multiagent systems based on linearized Turing's model
• Cospectrality preserving graph modifications and eigenvector properties via walk equivalence of vertices
• Nonvanishing minors of eigenvector matrices and consequences
• On a Conjecture of Godsil Concerning Controllable Random Graphs
• Note on graphs with irreducible characteristic polynomials
• Signed graphs whose all Laplacian eigenvalues are main
• Canonization of a random circulant graph by counting walks
• Controllability of NEPSes of graphs
• On the generalized spectral characterizations of Eulerian graphs
• The overgraphs of generalized cospectral controllable graphs
• Net Laplacian controllability for joins of signed graphs
• Generalized spectral characterization of graphs revisited
• Main Q-eigenvalues and generalized Q-cospectrality of graphs
• Cospectral graphs, GM-switching and regular rational orthogonal matrices of level \(p\)
• Spectral multiplicity functions of adjacency operators of graphs and cospectral infinite graphs
• scientific article; zbMATH DE number 7090165 (Why is no real title available?)
• Almost equitable partitions and new necessary conditions for network controllability
• A remark on the generalized spectral characterization of the disjoint union of graphs
• On strongly asymmetric and controllable primitive graphs
• Low-degree factors of random polynomials
• Construction of graphs with distinct eigenvalues
• Perfect state transfer in Laplacian quantum walk
• Controllability of undirected graphs
• On a theorem of Godsil and McKay concerning the construction of cospectral graphs
• Further results on almost controllable graphs

This page was built for publication: Controllable subsets in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1929751)