Construction of graphs being determined by their generalized Q-spectra

Abstract

Given a graph $G$ on $n$ vertices, its adjacency matrix and degree diagonal matrix are represented by $A(G)$ and $D(G)$, respectively. The $Q$-spectrum of $G$ consists of all the eigenvalues of its signless Laplacian matrix $Q(G)=A(G)+D(G)$ (including the multiplicities). A graph $G$ is known as being determined by its generalized $Q$-spectrum ($DGQS$ for short) if, for any graph $H$, $H$ and $G$ have the same $Q$-spectrum and so do their complements, then $H$ is isomorphic to $G$. In this paper, we present a method to construct $DGQS$ graphs. More specifically, let the matrix $W_Q(G)=\left[e,Qe,\dots ,Q^{n-1}e\right]$ ($e$ denotes the all-one column vector ) be the $Q$-walk matrix of $G$. It is shown that $G\circ P_k$ ($k=2,3$) is $DGQS$ if and only if $G$ is $DGQS$ for some specific graphs. This also provides a way to construct $DGQS$ graphs with more vertices by using $DGQS$ graphs with fewer vertices. At the same time, we also prove that $G\circ P_2$ is still $DGQS$ under specific circumstances. In particular, on the basis of the above results, we obtain an infinite sequences of $DGQS$ graphs $G\circ P_k^t$ ($k=2,3;t\ge 1$) for some specific $DGQS$ graph $G$.

15 pages, 1 figures