Connected graphs cospectral with a friendship graph

Document Type : Research Paper


University of Isfahan


‎Let $n$ be any positive integer‎, ‎the friendship graph $F_n$ consists of $n$ edge-disjoint triangles that all of them meeting in one vertex‎. ‎A graph $G$ is called cospectral with a graph $H$ if their adjacency matrices have the same eigenvalues‎. ‎Recently in \href{}{ /pdf/1310.6529v1.pdf} it is proved that if $G$ is any graph cospectral with $F_n$ ($n\neq 16$)‎, ‎then $G\cong F_n$‎. ‎Here we give a proof of a special case of the latter‎: ‎Any connected graph cospectral with $F_n$ is isomorphic to $F_n$‎. ‎Our proof is independent of ones given in \href{}{} and the proofs are based on our recent results given in [Trans‎. ‎Comb.‎, ‎ 2 no‎. ‎4 (2013) 37-52.] using an upper bound for the largest eigenvalue of a connected graph given in‎ ‎[J‎. ‎Combinatorial Theory Ser‎. ‎B, 81 (2001) 177-183.]‎.


Main Subjects

A. Abdollahi, S. Janbaz and M. R. Oboudi (2013). Graphs cospectral with a friendship graph or its complement. Trans. Comb.. 2 (4), 37-52
S. M. Cioaba, W. H. Haemers, J. Vermette and W. Wong (2013). The graphs with all but two eigenvalues equal to 1.
K. C. Das (2013). Proof of conjectures on adjacency eigenvalues of graphs. Discrete Math.. 313, 19-25
Y. Hong, J. Shu and K. Fang (2001). A sharp upper bound of the spectral radius of graphs. J. Combin. Theory Ser. B. 81, 177-183
J. F. Wang, F. Belardo, Q. X. Huang and B. Borovicanin (2010). On the two largest Q-eigenvalues of graphs. Discrete Math.. 310, 2858-2866
J. F. Wang, H. Zhao and Q. Huang (2012). Spectral characterization of multicone graphs. Czech. Math. J.. 62 (137), 117-126