On some graphs determined by their generalized spectrum

Abstract

A graph G is said to be determined by its generalized spectrum if for any graph H, H and G are cospectral with cospectral complements implies that H is isomorphic to G. In this paper, we investigate the enumeration formulas on the number of k-length walks (1 ≤ k ≤ 6) in a graph. It is shown that the numbers of subgraphs P₃, A₄ and C₄ (not necessarily induced) are invariants for generalized cospectral graphs. As an application of the new invariants, two kinds of expanded paths are proved to be determined by their generalized spectrum.