A classification of all 1-Salem graphs

Details A classification of all 1-Salem graphs A classification of all 1-Salem graphs

2011-09-28

arxiv.org/abs/1109.6275v1

Mathematics

Combinatorics

17 pages, 9 figures, 4 tables

Scientific paper

A cyclotomic graph is one that has all its eigenvalues in the interval $[-2,2]$, and a Salem graph is either (i) bipartite with all but two eigenvalues in $[-2,2]$, or (ii) non-bipartite with all but one eigenvalue in the interval $[-2,2]$. We define an $m$-Salem graph to be a connected Salem graph $G$ for which $m$ is minimal such that there exists an induced cyclotomic subgraph of $G$ that has $m$ fewer vertices than $G$. Every Salem graph contains a 1-Salem graph as an induced subgraph. The main result of this paper is a complete combinatorial description of all 1-Salem graphs: there are 25 infinite families and 383 sporadic examples, only 16 of which give trivial Salem graphs. We observe that all generalised line graphs that are Salem graphs contain at least one triangle, and hence produce a complete list of all 25 connected non-bipartite triangle-free Salem graphs.

Affiliated with

Also associated with

No associations

Rating

A classification of all 1-Salem graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A classification of all 1-Salem graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A classification of all 1-Salem graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-44295