One of the fundamental properties of a graph is the number of distinct eigenvalues of its adjacency or Laplace matrix. Determining this number is of theoretical interest as well as of practical ...impact. Sparse graphs with small spectra exhibit excellent structural properties and can act as interconnection topologies. In this paper, for any n we present graphs, for which the product of their vertex degree and the number of different eigenvalues is small. It is known that load balancing can be performed on such graphs in a small number of steps.
Provider: Czech digital library/Česká digitální knihovna - Institution: Academy of Sciences Library/Knihovna Akademie věd ČR - Data provided by Europeana Collections- Let $A(G)$ be the adjacency ...matrix of $G$. The characteristic polynomial of the adjacency matrix $A$ is called the characteristic polynomial of the graph $G$ and is denoted by $\phi (G, \lambda)$ or simply $\phi (G)$. The spectrum of $G$ consists of the roots (together with their multiplicities) $\lambda _1(G)\geq \lambda _2(G)\geq \ldots \geq \lambda _n(G)$ of the equation $\phi (G, \lambda )=0$. The largest root $\lambda _1(G)$ is referred to as the spectral radius of $G$. A $\ddag $-shape is a tree with exactly two of its vertices having maximal degree 4. We will denote by $G(l_1, l_2, \ldots , l_7)$ $(l_1\geq 0$, $l_i\geq 1$, $i=2,3,\ldots, 7)$ a $\ddag $-shape tree such that $G(l_1, l_2, \ldots , l_7)-u-v=P_{l_1}\cup P_{l_2}\cup \ldots \cup P_{l_7}$, where $u$ and $v$ are the vertices of degree 4. In this paper we prove that $3\sqrt {2}/{2}< \lambda _1(G(l_1, l_2, \ldots , l_7))< {5}/{2}$.- All metadata published by Europeana are available free of restriction under the Creative Commons CC0 1.0 Universal Public Domain Dedication. However, Europeana requests that you actively acknowledge and give attribution to all metadata sources including Europeana
PDF
