Decomposition of Smith graphs in maximal reflexive cacti Original Research Article

The spectrum of a graph is the family of eigenvalues of its image adjacency matrix. A simple graph is reflexive if its second largest eigenvalue image does not exceed 2. The graphic property image is a hereditary one, i.e. every induced subgraph of a reflexive graph preserves this property and that is why reflexive graphs are usually represented through maximal graphs. Cacti, or treelike graphs, are graphs whose all cycles are mutually edge-disjoint. The set of simple connected graphs characterized by the property image, where image is the largest eigenvalue, is known as the set of Smith graphs. It consists of cycles of all possible lengths and some trees. If two trees image and image have such vertices image and image which, after their identification image give a Smith tree, we say that that Smith tree can be split at its vertex image into image and image. It has turned out that several classes of maximal reflexive cacti can be described in the following way: we start from certain essential cyclic structure with two characteristic vertices image and image, and then form a family of maximal connected reflexive cacti by splitting Smith trees, and by attaching their parts to image and image. This way of decomposition of Smith trees leads to an interesting phenomenon of so-called pouring of Smith trees between two vertices.