5
$\begingroup$

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).]

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ The adjacency spectrum is $n$ $-1$s, $n-1$ $1$s, and the roots of $x^2=x+2n$. $\endgroup$
    – Will Sawin
    Commented Aug 6, 2012 at 22:06
  • $\begingroup$ 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. $\endgroup$
    – Jernej
    Commented Aug 7, 2012 at 17:46

2 Answers 2

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Where exactly is it stated that $F_n$ is determined by its spectrum for $ n \in \{2,3,4\}$ ? $\endgroup$
    – Jernej
    Commented Aug 7, 2012 at 17:32
  • $\begingroup$ @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. $\endgroup$
    – tergi
    Commented Aug 7, 2012 at 19:26
4
$\begingroup$

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

One may download it from

http://arxiv.org/abs/1310.6529

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .