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

$\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
    Aug 6 '12 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
    Aug 7 '12 at 17:46
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

$\endgroup$
2
  • $\begingroup$ Where exactly is it stated that $F_n$ is determined by its spectrum for $ n \in \{2,3,4\}$ ? $\endgroup$
    – Jernej
    Aug 7 '12 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
    Aug 7 '12 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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