Graphs whose Spectrum Determined by Non-constant Coefficients

Let G be a graph and M be a matrix associated with G whose characteristic polynomial is . We say that the spectrum of G is determined by non-constant coefficients (simply M-SDNC), if for any graph H with ai(H)=ai(G),0⩽i⩽n−1, then Spec(G)=Spec(H) (if M is the adjacency matrix or the Laplacian matrix of G, then G is called an A-SDNC graph or L-SDNC graph). In this paper, we study some properties of graphs which are A-SDNC or L-SDNC. Among other results, we prove that the path of order at least five is L-SDNC and moreover stars of order at least five are both A-SDNC and L-SDNC. Furthermore, we construct infinitely many trees which are not A-SDNC graphs. More precisely, we show that there are infinitely many pairs (T,T′) of trees such that A(T,x)−A(T′,x)=−1.