✦ LIBER ✦

On graphs with a fixed number of negative eigenvalues

✍ Scribed by Aleksander Torgašev

Publisher: Elsevier Science
Year: 1985
Tongue: English
Weight: 374 KB
Volume: 57
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(85)90184-0

No coin nor oath required. For personal study only.

✦ Synopsis

Let P(n) be the class of all connected graphs having exactly n ~> 1 negative eigenvalues (including their multiplicities). In this paper we prove that the class P(n) contains only finitely many so-called canonical graphs. The analogous statement for the class Q(n) of all connected graphs having exactly n positive eigenvalues is not valid. In addition, a structural connection between the classes P(n) and P(n + 1) is obtained.

📜 SIMILAR VOLUMES

Complex eigenvalues of a non-negative ma

Complex eigenvalues of a non-negative matrix with a specified graph

✍ R.B. Kellogg; A.B. Stephens 📂 Article 📅 1978 🏛 Elsevier Science 🌐 English ⚖ 456 KB

Note on the reconstruction of infinite g

Note on the reconstruction of infinite graphs with a fixed finite number of components

✍ Thomas Andreae 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 169 KB 👁 1 views

For every positive integer c , we construct a pair G, , H, of infinite, nonisomorphic graphs both having exactly c components such that G, and H, are hypomorphic, i.e., G, and H, have the same families of vertex-deleted subgraphs. This solves a problem of Bondy and Hemminger. Furthermore, the pair G

On the embedding of graphs into graphs w

On the embedding of graphs into graphs with few eigenvalues

✍ Vu, Van H. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 726 KB

A graph is called of type k if it is connected, regular, and has k distinct eigenvalues. For example graphs of type 2 are the complete graphs, while those of type 3 are the strongly regular graphs. We prove that for any positive integer n, every graph can be embedded in n cospectral, non-isomorphic

On rank three graphs with a large eigenv

On rank three graphs with a large eigenvalue

✍ Carl Bumiller 📂 Article 📅 1978 🏛 Elsevier Science 🌐 English ⚖ 337 KB

On the second eigenvalue of a graph

✍ A. Nilli 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 241 KB

Nilli, A., On the second eigenvalue of a graph, Discrete Mathematics 91 (1991) 207-210. It is shown that the second largest eigenvalue of the adjacency matrix of any G containing two edges the distance between which is at least 2k + 2 is at least (2G -l)/(k + 1).

Graphs with least number of colorings

✍ A. Sakaloglu; A. Satyanarayana 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 535 KB

## Abstract A λ‐coloring of a graph G is an assignment of λ or fewer colors to the points of G so that no two adjacent points have the same color. Let Ω (n,e) be the collection of all connected n‐point and e‐edge graphs and let Ωp(n,e) be the planar graphs of Ω(n, e). This paper characterizes the g