Research work · 2014

Connected graphs cospectral with a friendship graph

Aliréza Abdollahi, Shahrooz Janbaz

Transactions on combinatorics

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$ ($nneq 16$)‎, ‎then $Gcong 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.]‎.

Read free full text

DOI: 10.22108/toc.2014.4975