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 matrixcontrollabilitycontrollable pairswalks

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

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

Cited in

(51)

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

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)