ﻻ يوجد ملخص باللغة العربية
Let $G$ be an $n$-vertex graph with adjacency matrix $A$, and $W=[e,Ae,ldots,A^{n-1}e]$ be the walk matrix of $G$, where $e$ is the all-one vector. In Wang [J. Combin. Theory, Ser. B, 122 (2017): 438-451], the author showed that any graph $G$ is uniquely determined by its generalized spectrum (DGS) whenever $2^{-lfloor n/2 rfloor}det W$ is odd and square-free. In this paper, we introduce a large family of graphs $mathcal{F}_n={$ $n$-vertex graphs $Gcolon, 2^{-lfloor n/2 rfloor}det W =p^2b$ and rank$W=n-1$ over $mathbb{Z}/pmathbb{Z}},$ where $b$ is odd and square-free, $p$ is an odd prime and $p mid b$. We prove that any graph in $mathcal{F}_n$ either is DGS or has exactly one generalized cospectral mate up to isomorphism. Moreover, we show that the problem of finding the generalized cospectral mate for a graph in $mathcal{F}_n$ is equivalent to that of generating an appropriate rational orthogonal matrix from a given integral vector. This equivalence essentially depends on an amazing property of graphs in terms of generalized spectra, which states that any symmetric integral matrix generalized cospectral with the adjacency matrix of some graph must be an adjacency matrix. Based on this equivalence, we develop an efficient algorithm to decide whether a given graph in $mathcal{F}_n$ is DGS and further to find the unique generalized cospectral mate when it is not. We give some experimental results on graphs with at most 20 vertices, which suggest that $mathcal{F}_n$ may have a positive density (nearly $3%$) and possibly almost all graphs in $mathcal{F}_n$ are DGS as $nrightarrow infty$. This gives a supporting evidence for Haemers conjecture that almost all graphs are determined by their spectra.
We prove an upper bound on the number of pairwise strongly cospectral vertices in a normal Cayley graph, in terms of the multiplicities of its eigenvalues. We use this to determine an explicit bound in Cayley graphs of $mathbb{Z}_2^d$ and $mathbb{Z}_
In his survey Beyond graph energy: Norms of graphs and matrices (2016), Nikiforov proposed two problems concerning characterizing the graphs that attain equality in a lower bound and in a upper bound for the energy of a graph, respectively. We show t
A signed graph is a pair $(G,Sigma)$, where $G=(V,E)$ is a graph (in which parallel edges are permitted, but loops are not) with $V={1,ldots,n}$ and $Sigmasubseteq E$. The edges in $Sigma$ are called odd and the other edges of $E$ even. By $S(G,Sigma
Given a graph, we can form a spanning forest by first sorting the edges in some order, and then only keep edges incident to a vertex which is not incident to any previous edge. The resulting forest is dependent on the ordering of the edges, and so we
If the Laplacian matrix of a graph has a full set of orthogonal eigenvectors with entries $pm1$, then the matrix formed by taking the columns as the eigenvectors is a Hadamard matrix and the graph is said to be Hadamard diagonalizable. In this arti