Spectral analysis of Some Sequence-generated Graphs

Abstract

In the study of graph theory, there are some classes of graphs that can be coded by a sequence, sometimes called the creation sequence. A graph G is called H-free if H is not an induced subgraph of G. Many significant classes of graphs can be described in terms of forbidden subgraphs. They include threshold graphs, chain graphs, cographs, bipartite graphs, perfect graphs, chordal graphs, split graphs, and trees, to name a few. Very interestingly, only a few of them can be generated by a sequence. Trees, threshold graphs, chain graphs, and certain cographs are examples of such graphs. The notion of this sequence is commonly known as binary sequence in the case of threshold graphs and chain graphs. Threshold graph has forbidden subgraphs P4, C4, and 2K2; chain graph has forbidden subgraphs C3, C5 and 2K2; whereas cograph forbids P4. In this thesis, we investigate various spectral properties of these graphs: threshold, chain, and certain cographs. The primary matrices of this study are the adjacency matrix A, the Laplacian matrix L, and the Seidel matrix S. In particular, we analyse the Seidel spectrum of threshold graphs, the spectrum and energy of the Seidel matrix for chain graphs, and the adjacency and Laplacian spectrum of certain cographs. Consider a connected threshold graph G. The threshold graph has several equivalent definitions. In this study, we consider the definition based on binary strings that will be relevant to this work. The underlying matrix is the Seidel matrix S. We compute the determinant and a recurrence formula for the characteristic polynomial of S. A formula for the multiplicity of the Seidel eigenvalues _1 and the characterization of threshold graphs with at most five distinct Seidel eigenvalues are derived. Also, a class of Seidel integral threshold graphs is obtained. For a connected chain graph G, we study its Seidel characteristic polynomial, Seidel energy, and Seidel cospectral property. We show that 􀀀1 is always an eigenvalue of S and all other eigenvalues of S can have a multiplicity at most two. We obtain the multiplicity of the Seidel eigenvalue 􀀀1, minimum number of distinct eigenvalues, the eigenvalue bounds, and the lower and upper bounds of the Seidel energy of a chain graph. It is also shown that the energy bounds obtained here work better than the bounds conjectured by Haemers. An important result is that two non-switching equivalent chain graphs may be Seidel cospectral, and we obtain a class of such graphs. Also, the class of Seidel integral chain graphs is shown here. In the context of cographs, we establish that it is possible to link a creation sequence for a particular kind of cograph (we call this sub-class of cograph a mathcalC-graph). Such cographs are constructed from a limited sequence of positive integers. Using that sequence, we can determine the multiplicity of the eigenvalues 0, 􀀀1, and inertia of the cograph under investigation. An extended eigenvalue-free interval from (􀀀1; 0) to _􀀀1􀀀 P 2 2 ;􀀀1) [ (􀀀1; 0) [ (0; 􀀀1+ P 2 2 _min _, (where _min _ 1 is the least of all natural numbers in the creation sequence) is obtained for C-graphs. Additionally, we derive an exact formula for the characteristic polynomial. Finally, we investigate the Laplacian eigenvalues and eigenspaces, various connectivity parameters with extremal property and clique number of C-graphs. Finally, we make an attempt to find a connection between algebraic connectivity and clique number.