The graphs with all but two eigenvalues equal to ±1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\pm 1$$\end{document}

被引:0
作者
Sebastian M. Cioabă
Willem H. Haemers
Jason R. Vermette
Wiseley Wong
机构
[1] University of Delaware,Department of Mathematical Sciences
[2] Tilburg University,Department of Econometrics and Operations Research
[3] University of California,Department of Mathematics
[4] University of Maryland,undefined
关键词
Graph; Adjacency matrix; Friendship graph; Spectral characterization; 05B20; 05C50;
D O I
10.1007/s10801-014-0557-y
中图分类号
学科分类号
摘要
We determine all graphs whose adjacency matrices have at most two eigenvalues (multiplicities included) different from ±1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\pm 1$$\end{document} and decide which of these graphs are determined by their spectrum. This includes the so-called friendship graphs, which consist of a number of edge-disjoint triangles meeting in one vertex. It turns out that the friendship graph is determined by its spectrum, except when the number of triangles equals sixteen.
引用
收藏
页码:887 / 897
页数:10
相关论文
共 11 条
  • [1] Abdollahi A(2013)Graphs cospectral with a friendship graph or its complement Trans. Comb. 2 37-52
  • [2] Janbaz S(2003)Which graphs are determined by their spectrum? Linear Algebra Appl. 373 241-272
  • [3] Oboudi MR(2004)Combinatorial designs with two singular values-I: uniform multiplicative designs J. Comb. Theory A 107 127-142
  • [4] van Dam ER(2013)Proof of conjectures on adjacency eigenvalues of graphs Discr. Math. 313 19-25
  • [5] Haemers WH(1966)On a problem of graph theory Studia Sci. Math. Hung. 1 215-235
  • [6] van Dam ER(undefined)undefined undefined undefined undefined-undefined
  • [7] Spence E(undefined)undefined undefined undefined undefined-undefined
  • [8] Das KC(undefined)undefined undefined undefined undefined-undefined
  • [9] Erdős P(undefined)undefined undefined undefined undefined-undefined
  • [10] Rényi A(undefined)undefined undefined undefined undefined-undefined