Controllable subsets in graphs

DOI10.1007/S00026-012-0156-3zbMATH Open1256.05139arXiv1010.3231OpenAlexW2088872141MaRDI QIDQ1929751FDOQ1929751

Chris Godsil

Publication date: 9 January 2013

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

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.

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

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\)

zbMATH Keywords

adjacency matrixcontrollabilitywalkscontrollable pairs

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• A note on cospectral graphs
• A sufficient condition for a family of graphs being determined by their generalized spectra

Cited In (37)

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

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)