On strongly asymmetric and controllable primitive graphs

Abstract

A strongly asymmetric graph is a graph all of whose overgraphs are non-isomorphic. A graph whose 0–1 adjacency matrix has distinct and main eigenvalues is said to be controllable. We show that all controllable graphs are strongly asymmetric, thus strengthening the well-known result that controllable graphs have a trivial automorphism group. Moreover, we define the subclass of controllable primitive graphs (CP-graphs), and show that every controllable graph is either primitive or is the union or join of two controllable graphs. With the aid of CP-graphs, we prove that controllable graphs on at least six vertices have an induced path on four vertices. Furthermore, we show that the number of non-isomorphic controllable graphs and the number of non-isomorphic controllable primitive graphs on n ≥ 2 vertices are both even. Using a computer search, we show that most of the controllable graphs on up to ten vertices are primitive. Among the controllable graphs on n < 12 vertices, the controllable non-primitive graphs are proved to be related to the singular controllable graphs on n − 1 vertices.