Graphs cospectral with a friendship graph or its complement

MaRDI QIDQ2933527zbMATH OpenFDO

Authors Alireza Abdollahi, Shahrooz Janbaz, Mohammad Reza Oboudi

Publication date 3 December 2014

Full work available at URL https://arxiv.org/abs/1307.5411

zbMATH Keywords

adjacency eigenvaluescospectral graphsfriendship graphs

Mathematics Subject Classification ID

Graph polynomials (05C31) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

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

Recommendations

• Connected graphs cospectral with a friendship graph
• The graphs with all but two eigenvalues equal to \(\pm 1\)
• The spectral determinations of the join of two friendship graphs
• The spectral determinations of some classes of multicone graphs
• The spectral characterization of the connected multicone graphs \(K_w \nabla mK_{n,n}\)

Cited in

(16)

• Constructing Clifford algebras for windmill and Dutch windmill graphs; a new proof of the friendship theorem
• Principal eigenvector localization and centrality in networks: revisited
• The graphs with all but two eigenvalues equal to \(\pm 1\)
• The graphs with all but two eigenvalues equal to \(-2\) or 0
• Doubling constants and spectral theory on graphs
• Groups all of whose undirected Cayley graphs are determined by their spectra
• Core-satellite graphs: clustering, assortativity and spectral properties
• WEIGHT-DEPENDENT WALKS AND AVERAGE SHORTEST WEIGHTED PATH ON THE WEIGHTED ITERATED FRIENDSHIP GRAPHS
• On the number of perfect matchings of generalized theta graphs and the edge cover polynomials of friendship graphs
• A large family of cospectral Cayley graphs over dihedral groups
• Connected graphs cospectral with a friendship graph
• On the spectral determinations of the connected multicone graphs \(K_r \nabla sK_t\)
• The graphs with exactly two distance eigenvalues different from -1 and -3
• Spectral radii of friendship graphs and their connected induced subgraphs
• Module structures on L-algebras
• When local and global clustering of networks diverge

This page was built for publication: Graphs cospectral with a friendship graph or its complement

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2933527)