We obtain spectral properties of the Pascal graphs by exploring its spectral graph invariants such as the algebraic connectivity, the first three largest Laplacian eigenvalues and the nullity. Some open problems pertaining to the Pascal graphs are given.

This paper was initiated by the observation that chordal Toeplitz graphs $T_n\langle t_1, \ldots, t_k\rangle$ with $n > t_{k-1}+t_k$ are claw-free. A Toeplitz graph with $n$ vertices is a simple graph whose adjacency matrix is an $n\times n$ $(0,1)$-symmetric Toeplitz matrix with zero diagonal and a claw in a graph means a star $K_{1,3}$ as an induced subgraph. We find an interesting family of claw-free Toeplitz graphs so called `cocoonery' and show that if $n > t_{k-1}+t_k$, then this family becomes exactly the family of claw-free Toeplitz graphs. We also completely characterize a claw-free Toeplitz graph $T_n\langle t_1, \ldots, t_k\rangle$ for $k=2$ and $k=3$. We go further to study Toeplitz graphs which happen to be line graphs.

The authors of this paper have used the theory of Riordan matrices to introduce the notion of a Riordan graph in \cite{CJKM}. Riordan graphs are proved to have a number of interesting (fractal) properties, and they are a far-reaching generalization of the well known and well studied Pascal graphs and Toeplitz graphs, and also some other families of graphs. The main focus in \cite{CJKM} is the study of structural properties of families of Riordan graphs obtained from certain infinite Riordan graphs. In this paper, we use a number of results in~\cite{CJKM} to study spectral properties of Riordan graphs. Our studies include, but are not limited to the spectral graph invariants for Riordan graphs such as the adjacency eigenvalues, (signless) Laplacian eigenvalues, nullity, positive and negative inertias, and rank. We also study determinants of Riordan graphs, in particular, giving results about determinants of Catalan graphs.

In this paper, we use the theory of Riordan matrices to introduce the notion of a Riordan graph. The Riordan graphs are a far-reaching generalization of the well known and well studied Pascal graphs and Toeplitz graphs, and also some other families of graphs. The Riordan graphs are proved to have a number of interesting (fractal) properties, which can be useful in creating computer networks with certain desirable features, or in obtaining useful information when designing algorithms to compute values of graph invariants. The main focus in this paper is the study of structural properties of families of Riordan graphs obtained from infinite Riordan graphs, which includes a fundamental decomposition theorem and certain conditions on Riordan graphs to have an Eulerian trail/cycle or a Hamiltonian cycle. We will study spectral properties of the Riordan graphs in a follow up paper.