# Can the friendship graph be determind by its adjacency spectrum?

Let $n\geq 1$ be an integer. The Friendship Graph (or Dutch windmill graph or $n$-Fan) $F_n$ is a graph that can be constructed by coalescence $n$ copies of the cycle graph $C_3$ with a common vertex. By construction, the friendship graph $F_n$ is isomorphic to the windmill graph $Wd\left(3,n\right)$.

Can $F_n$ be determined by its adjacency spectrum? By the adjacency spectrum of a graph, we mean the multiset of the eigenvalues of the adjacency matrix of the graph. For a graph $G$, we denote by $Spec(G)$ its adjacency spectrum. A graph $G$ is said to be determined by its adjacency spectrum, if $Spec(G)=Spec(H)$ for some graph $H$, then $G\cong H$.

It is known that the friendship graph can be determined by the signless Laplacian spectrum. See [Discrete Math. 310, No. 21, 2858-2866 (2010).]

• The adjacency spectrum is $n$ $-1$s, $n-1$ $1$s, and the roots of $x^2=x+2n$. Aug 6 '12 at 22:06
• Some obvious remarks. In general it is hard to prove that a graph is determined by its spectrum. If you start looking for a counterexample you need only consider graphs having precisely $n$ triangles. Aug 7 '12 at 17:46

This isn't a real answer, but wolfram-alpha says that $F_n$ is determined by its (adjacency) spectrum for $n \in \lbrace 2,3,4 \rbrace$. It doesn't say anything about $n=5$.

http://www.wolframalpha.com/input/?i=%285%2C3%29-windmill+graph

• Where exactly is it stated that $F_n$ is determined by its spectrum for $n \in \{2,3,4\}$ ? Aug 7 '12 at 17:32
• @Jernej: "graph features" of (2,3)-, (3,3), and (4,3)-windmill graphs include "determined by spectrum" (meaning adjacency spectrum) in wolfram alpha. The link in the answer above goes to a (5,3)-windmill graph which does not mention such a graph feature, probably because wolfram-alpha doesn't know the answer. Aug 7 '12 at 19:26

This is answered in the following recent paper:

The graphs with all but two eigenvalues equal to ±1

By Sebastian M. Cioabă, Willem H. Haemers, Jason Vermette, Wiseley Wong

The answer is no! But there is only one exception that is $F_{16}$ and all other friendship graphs can be determined by spectrum.