Graphs cospectral with a friendship graph or its complement

Document Type: Research Paper

Authors

University of Isfahan

Abstract

‎Let $n$ be any positive integer and $F_n$ be the friendship (or Dutch windmill) graph with $2n+1$ vertices and $3n$ edges‎. ‎Here we study graphs with the same adjacency spectrum as $F_n$‎. ‎Two graphs are called cospectral if the eigenvalues multiset of their adjacency matrices are the same‎. ‎Let $G$ be a graph cospectral with $F_n$‎. ‎Here we prove that if $G$ has no cycle of length $4$ or $5$‎, ‎then $G\cong F_n$‎. ‎Moreover if $G$ is connected and planar then $G\cong F_n$‎. ‎All but one of connected components of $G$ are isomorphic to $K_2$‎. ‎The complement $\overline{F_n}$ of the friendship graph is determined by its adjacency eigenvalues‎, ‎that is‎, ‎if $\overline{F_n}$ is cospectral with a graph $H$‎, ‎then $H\cong \overline{F_n}$‎.

Keywords

Main Subjects