Connected graphs cospectral with a friendship graph

Document Type: Research Paper

Authors

University of Isfahan

Abstract

‎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{http://arxiv.org/pdf/1310.6529v1.pdf}{http://arxiv.org /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{http://arxiv.org/pdf/1310.6529v1.pdf}{http://arxiv.org/pdf/1310.6529v1.pdf} 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.]‎.

Keywords

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. http://arxiv.org/pdf/1310.6529v1.pdf.
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