# Graphs cospectral with a friendship graph or its complement

Transactions on Combinatorics. 2013;2(4):37-52

Journal Homepage

Journal Title: Transactions on Combinatorics

ISSN: 2251-8657 (Print); 2251-8665 (Online)

Publisher: University of Isfahan

LCC Subject Category: Science: Mathematics

Country of publisher: Iran, Islamic Republic of

Language of fulltext: English

Full-text formats available: PDF

AUTHORS

Alireza Abdollahi
Shahrooz Janbaz

EDITORIAL INFORMATION

Editorial Board

Instructions for authors

Time From Submission to Publication: 30 weeks

Abstract | Full Text

Let \$n\$ be any positive integer and let \$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 the \$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 \$Gcong F_n\$. Moreover if \$G\$ is connected and planar then \$Gcong 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 \$Hcong overline{F_n}\$.