Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
2  
The adjacency spectrum is $n$ $-1$s, $n-1$ $1$s, and the roots of $x^2=x+2n$. –  Will Sawin 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. –  Jernej Aug 7 '12 at 17:46

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
    
Where exactly is it stated that $F_n$ is determined by its spectrum for $ n \in \{2,3,4\}$ ? –  Jernej 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. –  tergi 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

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.