pith. sign in

arxiv: 1307.5411 · v1 · pith:XT65WM7Onew · submitted 2013-07-20 · 🧮 math.CO

Graphs cospectral with a friendship graph or its complement

classification 🧮 math.CO
keywords graphcospectraladjacencycongfriendshipgraphsthencomplement
0
0 comments X
read the original abstract

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 $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 $\bar{F_n}$ of the friendship graph is determined by its adjacency eigenvalues, that is, if $\bar{F_n}$ is cospectral with a graph $H$, then $H\cong \bar{F_n}$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.