The new upper bounds on the spectral radius of weighted graphs

Let us consider weighted graphs, where the weights of the edges are positive definite matrices. The eigenvalues of a weighted graph are the eigenvalues of its adjacency matrix and the spectral radius of a weighted graph is also the spectral radius of its adjacency matrix. In this paper, we obtain two upper bounds for the spectral radius of weighted graphs and compare with a known upper bound. We also characterize graphs for which the upper bounds are attained.     

A sharp upper bound on the spectral radius of weighted graphs

We consider weighted graphs, where the edge weights are positive definite matrices. The eigenvalues of a graph are the eigenvalues of its adjacency matrix. We obtain an upper bound on the spectral radius of the adjacency matrix and characterize graphs for which the bound is attained.     

Extremal graph characterization from the bounds of the spectral radius of weighted graphs

We consider weighted graphs, where the edge weights are positive definite matrices. The eigenvalues of a graph are the eigenvalues of its adjacency matrix. We obtain a lower bound and an upper bound on the spectral radius of the adjacency matrix of weighted graphs and characterize graphs for which the bounds are attained.     

非负矩阵与有向图的谱半径

本文给出非负矩阵的谱半径的上界、下界,由此给出有向图的谱半径的界.     

Halin图谱半径的新上界及极图

利用移接变形的方法再结合特征值的计算技巧刻画出Halin图中谱半径达到第二大的极图,从而得到除轮图以外的Halin图的谱半径的上界以及极图.     

Spectral Radius of Non-negative Matrices and Digraphs

We present an upper and a lower bound for the spectral radius of non-negative matrices. Then we give the bounds for the spectral radius of digraphs. Received February 10, 1999, Revised November 13, 2000, Accepted March 5, 2001     

关于赋权树的谱半径的精确上界

The spectrum of weighted graphs are often used to solve the problems in the design of networks and electronic circuits. In this paper, we derive the sharp upper bound of spectral radius of all weighted trees on given order and edge independence number, and obtain all such trees that their spectral radius reach the upper bound.     

随机图的谱矩

简单图G的k阶谱矩定义为G的特征值的k阶幂之和,记为Mk(G).应用概率和代数的方法,对于几乎所有的图G,本文给出Mk(G)的一个精确估计.此外,对于几乎所有的多部图G,本文给出了Mk(G)的上界和下界.     

On an upper bound of the spectral radius of graphs

We give some upper bounds for the spectral radius of bipartite graph and graph, which improve the result in Hong’s Paper [Y. Hong, J.-L. Shu, K. Fang, A sharp upper bound of the spectral radius of graphs, J. Combin. Theory Ser. B 81 (2001) 177-183].     

给定独立数的连通图的无符号Laplace谱半径(英文)

本文刻画取得给定阶数和独立数连通图的谱半径最大值的图的结构,对特殊独立数也给出取得最小谱半径图的结构.     

Extremal graph characterization from the upper bound of the Laplacian spectral radius of weighted graphs

We consider weighted graphs, where the edge weights are positive definite matrices. In this paper, we obtain two upper bounds on the spectral radius of the Laplacian matrix of weighted graphs and characterize graphs for which the bounds are attained. Moreover, we show that some known upper bounds on the Laplacian spectral radius of weighted and unweighted graphs can be deduced from our upper bounds.     

Upper and lower bounds for the energy of bipartite graphs

Using Lagrange's multiplier rule, we find upper and lower bounds of the energy of a bipartite graph G, in terms of the number of vertices, edges and the spectral moment of fourth order. Moreover, the upper bound is attained in a graph G if and only if G is the graph of a symmetric balanced incomplete block design (BIBD). Also, we determine the graphs for which the lower bound is sharp.     

Lower bounds on the spectra of symmetric matrices with nonnegative entries

If we normalize a symmetric n × n matrix with nonnegative entriesso that its largest entry is 1, then its spectrum is bounded below by $\text{?n}\text{2}$. The lower bound is achieved in all even dimensions for (and only for) adjacency matrices of complete bipartite graphs with equal parts.     

Theorems on partitioned matrices revisited and their applications to graph spectra

Some old results about spectra of partitioned matrices due to Goddard and Schneider or Haynsworth are re-proved. A new result is given for the spectrum of a block-stochastic matrix with the property that each off-diagonal block has equal entries and each diagonal block has equal diagonal entries and equal off-diagonal entries. The result is applied to the study of the spectra of the usual graph matrices by partitioning the vertex set of the graph according to the neighborhood equivalence relation. The concept of a reduced graph matrix is introduced. The question of when n-2 is the second largest signless Laplacian eigenvalue of a connected graph of order n is treated. A recent conjecture posed by Tam, Fan and Zhou on graphs that maximize the signless Laplacian spectral radius over all (not necessarily connected) graphs with given numbers of vertices and edges is refuted. The Laplacian spectrum of a (degree) maximal graph is reconsidered.     

STRONG EMBEDDINGS OF PLANAR GRAPHS ON HIGHER SURFACES

In this paper, the authors discuss the upper bound for the genus of strong embeddings for 3-connected planar graphs on higher surfaces. It is shown that the problem of determining the upper bound for the strong embedding of 3-connected planar near-triangulations on higher non-orientable surfaces is NP-hard. As a corollary, a theorem of Richter, Seymour and Siran about the strong embedding of 3-connected planar graphs is generalized to orientable surface.     

The band spectrum of the periodic Airy–Schrödinger operator on the real line

We introduce the periodic Airy–Schrödinger operator and we describe its band spectrum. This is an example of solvable model with a periodic potential which is not differentiable at its extrema. We prove that there exists a sequence of explicit constants giving upper bounds of the semiclassical parameter for which explicit estimates are valid. We completely determine the behaviour of the edges of the first spectral band with respect to the semiclassical parameter. Then, we investigate the spectral bands and gaps situated in the range of the potential. We prove precise estimates on the widths of these spectral bands and these spectral gaps and we determine an upper bound on the integrated spectral density in this range. Finally, we get estimates of the edges of spectral bands and thus of the widths of spectral bands and spectral gaps which are stated for values of the semiclassical parameter in fixed intervals.     

Lower Bounds on the (Laplacian) Spectral Radius of Weighted Graphs

The weighted graphs, where the edge weights are positive numbers, are considered. The authors obtain some lower bounds on the spectral radius and the Laplacian spectral radius of weighted graphs, and characterize the graphs for which the bounds are attained. Moreover, some known lower bounds on the spectral radius and the Laplacian spectral radius of unweighted graphs can be deduced from the bounds.     

Spectral methods for graph clustering - A survey

Graph clustering is an area in cluster analysis that looks for groups of related vertices in a graph. Due to its large applicability, several graph clustering algorithms have been proposed in the last years. A particular class of graph clustering algorithms is known as spectral clustering algorithms. These algorithms are mostly based on the eigen-decomposition of Laplacian matrices of either weighted or unweighted graphs. This survey presents different graph clustering formulations, most of which based on graph cut and partitioning problems, and describes the main spectral clustering algorithms found in literature that solve these problems.     

On the spectral characterization of the union of complete multipartite graph and some isolated vertices

A graph is said to be determined by its adjacency spectrum (DS for short) if there is no other non-isomorphic graph with the same spectrum. In this paper, we focus our attention on the spectral characterization of the union of complete multipartite graph and some isolated vertices, and all its cospectral graphs are obtained. By the results, some complete multipartite graphs determined by their adjacency spectrum are also given. This extends several previous results of spectral characterization related to the complete multipartite graphs.     

Zero forcing sets and bipartite circulants

In this paper we introduce a class of regular bipartite graphs whose biadjacency matrices are circulant matrices – a generalization of circulant graphs which happen to be bipartite – and we describe some of their properties. Notably, we compute upper and lower bounds for the zero forcing number for such a graph based only on the parameters that describe its biadjacency matrix. The main results of the paper characterize the bipartite circulant graphs that achieve equality in the lower bound and compute their minimum ranks.