|
Mathematics
On spectrum of an adjacencies matrix of almost-complete graph
S. V. Kozlukov Voronezh State University
Abstract:
Let $\mathcal{A}_{MN}$ be a $N \times N$ matrix composed of $N^2-M$ unities and $M$ zeroes. Considered as an adjacencies matrix, $\mathcal{A}_{MN}$ corresponds to a complete digraph with loops on $N$ vertices with some $M$ out of $N^2$ edges removed. Someimportant properties of a graph are determined by its spectrum. For example Wang et al. [4] proposed a discrete-time model of viral propagation in a network. In that model a virus will die out or linger on depending on whether the ratio of curing and infection rates is below or above the treshold value. As Wang et al. have shown that treshold value is the spectral radius of the adjacencies matrix of the network graph, i.e. the maximal absolute value of its eigenvalues. More comprehensive description of spectral graph theory and its application is given by Cv`etkovic et al. [3].
This article analyzes spectral properties of such matrices. The matrix $\mathcal{A}_{MN}$ can be represented in the form $\mathcal{A}_{MN}=\mathcal{J}_N-\mathfrak{B}_{MN}$, where $\mathcal{J}_N$ is a $N \times N$ matrix whose all entries are ones and $\mathfrak{B}_{MN}$ has unities exactly at these $M$ places where $\mathcal{A}_{MN}$ has zeroes. The spectrum of $\mathcal{J}_N$ can be easily computed: $\mathcal{J}_N^2=N\mathcal{J}$ , so $\lambda$ is the minimal annihilating polynomial of $\mathcal{J}_N$ and hence the spectrum of $\mathcal{J}_N$ is $\sigma(\mathcal{J}_N)=\{0,N\}$.
For small enough $M$ the eigenvalues of $\mathcal{A}_{MN}$ will be “close” to those of $\mathcal{J}_N$. Then The Method of Similar Operators [1; 2] is used, which allows in the case of perturbation of some ideal object (whose properties are known) to find an element of the algebra under consideration similar to the disturbed one yet having “simpler” structure. Via this method the following theorem is proven:
Theorem. Let $M<\frac{N^2}{16}$, then the spectrum of $\mathcal{A}_{MN}$ can be represented as a disjoint union $\sigma(\mathcal{A}_{MN})=\sigma_1\cup \sigma_2$ of a singletone $\sigma_1=\{\lambda_1\}$ and the set $\sigma_2$, satisfying the following conditions:
$$
\sigma_1\subset\{\mu\in\mathbb{R};|\mu-N|<4\sqrt{M}\},
$$
$$
\sigma_2\subset\{\mu\in\mathbb{C};|\mu|<4\sqrt{M}\}.
$$
Keywords:
the method of similar operators, graph spectra, eigenvalues
localization, Jordan normal form, nonlinear equations, contraction theory.
Citation:
S. V. Kozlukov, “On spectrum of an adjacencies matrix of almost-complete graph”, Mathematical Physics and Computer Simulation, 20:4 (2017), 18–25
Linking options:
https://www.mathnet.ru/eng/vvgum193 https://www.mathnet.ru/eng/vvgum/v20/i4/p18
|
|