Eigenvalue bounds for some classes of matrices associated with graphs

Ranjit Mehatari; M. Rajesh Kannan

Displaying similar documents to “Eigenvalue bounds for some classes of matrices associated with graphs”

Main eigenvalues of real symmetric matrices with application to signed graphs

Zoran Stanić (2020)

Czechoslovak Mathematical Journal

Similarity:

An eigenvalue of a real symmetric matrix is called main if there is an associated eigenvector not orthogonal to the all-1 vector $𝐣$ . Main eigenvalues are frequently considered in the framework of simple undirected graphs. In this study we generalize some results and then apply them to signed graphs.

On graphs whose second least eigenvalue is at least $- 1$

M. Petrović (1990)

Matematički Vesnik

Similarity:

A lower bound sequence for the minimum eigenvalue of Hadamard product of an $M$ -matrix and its inverse

Wenlong Zeng, Jianzhou Liu (2022)

Czechoslovak Mathematical Journal

Similarity:

We propose a lower bound sequence for the minimum eigenvalue of Hadamard product of an $M$ -matrix and its inverse, in terms of an $S$ -type eigenvalues inclusion set and inequality scaling techniques. In addition, it is proved that the lower bound sequence converges. Several numerical experiments are given to demonstrate that the lower bound sequence is sharper than some existing ones in most cases.

Some properties complementary to Brualdi-Li matrices

Chuanlong Wang, Xuerong Yong (2015)

Czechoslovak Mathematical Journal

Similarity:

In this paper we derive new properties complementary to an $2 n \times 2 n$ Brualdi-Li tournament matrix $B_{2 n}$ . We show that $B_{2 n}$ has exactly one positive real eigenvalue and one negative real eigenvalue and, as a by-product, reprove that every Brualdi-Li matrix has distinct eigenvalues. We then bound the partial sums of the real parts and the imaginary parts of its eigenvalues. The inverse of $B_{2 n}$ is also determined. Related results obtained in previous articles are proven to be corollaries.

Inverse eigenvalue problem for constructing a kind of acyclic matrices with two eigenpairs

Maryam Babaei Zarch, Seyed Abolfazl Shahzadeh Fazeli, Seyed Mehdi Karbassi (2020)

Applications of Mathematics

Similarity:

We investigate an inverse eigenvalue problem for constructing a special kind of acyclic matrices. The problem involves the reconstruction of the matrices whose graph is an $m$ -centipede. This is done by using the $(2 m - 1)$ st and $(2 m)$ th eigenpairs of their leading principal submatrices. To solve this problem, the recurrence relations between leading principal submatrices are used.

Roughness in $G$ -graphs

Bibi N. Onagh (2020)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

$G$ -graphs are a type of graphs associated to groups, which were proposed by A. Bretto and A. Faisant (2005). In this paper, we first give some theorems regarding $G$ -graphs. Then we introduce the notion of rough $G$ -graphs and investigate some important properties of these graphs.

Metrically regular square of metrically regular bipartite graphs of diameter $D = 7$

Vladimír Vetchý (2018)

Archivum Mathematicum

Similarity:

The present paper deals with the spectra of powers of metrically regular graphs. We prove that there is only two tables of the parameters of an association scheme so that the corresponding metrically regular bipartite graph of diameter $D = 7$ (8 distinct eigenvalues of the adjacency matrix) has the metrically regular square. The results deal with the graphs of the diameter $D < 7$ see [8], [9] and [10].

2-halvable complete 4-partite graphs

Dalibor Fronček (1998)

Discussiones Mathematicae Graph Theory

Similarity:

A complete 4-partite graph $K_{m ₁, m ₂, m ₃, m ₄}$ is called d-halvable if it can be decomposed into two isomorphic factors of diameter d. In the class of graphs $K_{m ₁, m ₂, m ₃, m ₄}$ with at most one odd part all d-halvable graphs are known. In the class of biregular graphs $K_{m ₁, m ₂, m ₃, m ₄}$ with four odd parts (i.e., the graphs $K_{m, m, m, n}$ and $K_{m, m, n, n}$ ) all d-halvable graphs are known as well, except for the graphs $K_{m, m, n, n}$ when d = 2 and n ≠ m. We prove that such graphs are 2-halvable iff n,m ≥ 3. We also determine a new class of non-halvable graphs $K_{m ₁, m ₂, m ₃, m ₄}$ with three...

New bounds on the Laplacian spectral ratio of connected graphs

Zhen Lin, Min Cai, Jiajia Wang (2024)

Czechoslovak Mathematical Journal

Similarity:

Let $G$ be a simple connected undirected graph. The Laplacian spectral ratio of $G$ is defined as the quotient between the largest and second smallest Laplacian eigenvalues of $G$ , which is an important parameter in graph theory and networks. We obtain some bounds of the Laplacian spectral ratio in terms of the number of the spanning trees and the sum of powers of the Laplacian eigenvalues. In addition, we study the extremal Laplacian spectral ratio among trees with $n$ vertices, which improves...

Radio k-labelings for Cartesian products of graphs

Mustapha Kchikech, Riadh Khennoufa, Olivier Togni (2008)

Discussiones Mathematicae Graph Theory

Similarity:

Frequency planning consists in allocating frequencies to the transmitters of a cellular network so as to ensure that no pair of transmitters interfere. We study the problem of reducing interference by modeling this by a radio k-labeling problem on graphs: For a graph G and an integer k ≥ 1, a radio k-labeling of G is an assignment f of non negative integers to the vertices of G such that $| f (x) - f (y) | \geq k + 1 - d_{G} (x, y)$ , for any two vertices x and y, where $d_{G} (x, y)$ is the distance between x and y in G. The radio k-chromatic...

Partial sum of eigenvalues of random graphs

Israel Rocha (2020)

Applications of Mathematics

Similarity:

Let $G$ be a graph on $n$ vertices and let $λ_{1} \geq λ_{2} \geq ... \geq λ_{n}$ be the eigenvalues of its adjacency matrix. For random graphs we investigate the sum of eigenvalues $s_{k} = \sum_{i = 1}^{k} λ_{i}$ , for $1 \leq k \leq n$ , and show that a typical graph has $s_{k} \leq (e (G) + k^{2}) / {(0.99 n)}^{1 / 2}$ , where $e (G)$ is the number of edges of $G$ . We also show bounds for the sum of eigenvalues within a given range in terms of the number of edges. The approach for the proofs was first used in Rocha (2020) to bound the partial sum of eigenvalues of the Laplacian matrix.

An improvement of an inequality of Fiedler leading to a new conjecture on nonnegative matrices

Assaf Goldberger, Neumann, Michael (2004)

Czechoslovak Mathematical Journal

Similarity:

Suppose that $A$ is an $n \times n$ nonnegative matrix whose eigenvalues are $λ = ρ (A), λ_{2}, ..., λ_{n}$ . Fiedler and others have shown that $det (λ I - A) \leq λ^{n} - ρ^{n}$ , for all $λ > ρ$ , with equality for any such $λ$ if and only if $A$ is the simple cycle matrix. Let $a_{i}$ be the signed sum of the determinants of the principal submatrices of $A$ of order $i \times i$ , $i = 1, ..., n - 1$ . We use similar techniques to Fiedler to show that Fiedler’s inequality can be strengthened to: $det (λ I - A) + \sum_{i = 1}^{n - 1} ρ^{n - 2 i} | a_{i} | {(λ - ρ)}^{i} \leq λ^{n} - ρ^{n}$ , for all $λ \geq ρ$ . We use this inequality to derive the inequality that: $\prod_{2}^{n} (ρ - λ_{i}) \leq ρ^{n - 2} \sum_{i = 2}^{n} (ρ - λ_{i})$ . In the spirit of a celebrated conjecture...