Some results on the ordering of the Laplacian spectral radii of unicyclic graphs

A unicyclic graph is a graph whose number of edges is equal to the number of vertices. Guo Shu-Guang [S.G. Guo, The largest Laplacian spectral radius of unicyclic graph, Appl. Math. J. Chinese Univ. Ser. A. 16 (2) (2001) 131–135] determined the first four largest Laplacian spectral radii together with the corresponding graphs among all unicyclic graphs on n vertices. In this paper, we extend this ordering by determining the fifth to the ninth largest Laplacian spectral radii together with the corresponding graphs among all unicyclic graphs on n vertices.     

The distance spectrum of the path Pn and The First Distance Eigenvector of Connected Graphs

Forumulas are given for all of the eigenvalues and eigenvectors of the distance matrix of the path P_n on n vertices. It is shown that P_n has the maximum distance spectral radius among all connected graphs of order n, and an ordering property of the entries of the Perron-Frobenius eigenvector is presented.     

The distance spectrum of the path Pn and The First Distance Eigenvector of Connected Graphs

Forumulas are given for all of the eigenvalues and eigenvectors of the distance matrix of the path P_n on n vertices. It is shown that P_n has the maximum distance spectral radius among all connected graphs of order n, and an ordering property of the entries of the Perron-Frobenius eigenvector is presented.     

A graphon approach to limiting spectral distributions of Wigner‐type matrices

We present a new approach, based on graphon theory, to finding the limiting spectral distributions of general Wigner‐type matrices. This approach determines the moments of the limiting measures and the equations of their Stieltjes transforms explicitly with weaker assumptions on the convergence of variance profiles than previous results. As applications, we give a new proof of the semicircle law for generalized Wigner matrices and determine the limiting spectral distributions for three sparse inhomogeneous random graph models with sparsity ω(1/n): inhomogeneous random graphs with roughly equal expected degrees, W‐random graphs and stochastic block models with a growing number of blocks. Furthermore, we show our theorems can be applied to random Gram matrices with a variance profile for which we can find the limiting spectral distributions under weaker assumptions than previous results.     

树和单圈图的斜谱矩

给定图$G$,对图$G$的每条边确定一个方向,称为$G$的定向图$G^\sigma$, $G$称为$G^\sigma$的基础图. $G^\sigma$的斜邻接矩阵$S(G^\sigma)$是反对称矩阵,其特征值是0或纯虚数. $S(G^\sigma)$所有特征值的$k$次幂之和称为$G^\sigma$的$k$阶斜谱矩,其中$k$是非负整数.斜谱矩序列可用于对图进行排序.本文主要研究定向树和定向单圈图的斜谱矩,并对这两类图的斜谱矩序列依照字典序进行排序.首先确定了直径为$d$的树作为基础图的所有定向树中,斜谱矩序最大的$2\lfloor\frac{d}{4}\rfloor$个图; 然后确定以围长为$g$的单圈图作为基础图的所有定向单圈图中, 斜谱矩序最大的$2\lfloor\frac{g}{4}\rfloor+1$个图.     

Graph presentations for moments of noncentral Wishart distributions and their applications

We provide formulas for the moments of the real and complex noncentral Wishart distributions of general degrees. The obtained formulas for the real and complex cases are described in terms of the undirected and directed graphs, respectively. By considering degenerate cases, we give explicit formulas for the moments of bivariate chi-square distributions and 2 × 2 Wishart distributions by enumerating the graphs. Noting that the Laguerre polynomials can be considered to be moments of a noncentral chi-square distributions formally, we demonstrate a combinatorial interpretation of the coefficients of the Laguerre polynomials.     

Obstruction sets for outer‐cylindrical graphs

A graph is outer‐cylindrical if it embeds in the sphere so that there are two distinct faces whose boundaries together contain all the vertices. The class of outer‐cylindrical graphs is closed under minors. We give the complete set of 38 minor‐minimal non‐outer‐cylindrical graphs, or equivalently, an excluded minor characterization of outer‐cylindrical graphs. We also give the obstruction sets under the related topological ordering and Y Δ‐ordering. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 42–64, 2001     

Ramsey Numbers for Partially-Ordered Sets

We present a refinement of Ramsey numbers by considering graphs with a partial ordering on their vertices. This is a natural extension of the ordered Ramsey numbers. We formalize situations in which we can use arbitrary families of partially-ordered sets to form host graphs for Ramsey problems. We explore connections to well studied Turán-type problems in partially-ordered sets, particularly those in the Boolean lattice. We find a strong difference between Ramsey numbers on the Boolean lattice and ordered Ramsey numbers when the partial ordering on the graphs have large antichains.     

Spectral properties of Pascal graphs

We obtain spectral properties of the Pascal graphs by exploring its spectral graph invariants such as the algebraic connectivity, the first three largest Laplacian eigenvalues and the nullity. Some open problems pertaining to the Pascal graphs are given.     

The signless Laplacian spectral radius of graphs with given degree sequences

In this paper, we investigate the properties of the largest signless Laplacian spectral radius in the set of all simple connected graphs with a given degree sequence. These results are used to characterize the unicyclic graphs that have the largest signless Laplacian spectral radius for a given unicyclic graphic degree sequence. Moreover, all extremal unicyclic graphs having the largest signless Laplacian spectral radius are obtained in the sets of all unicyclic graphs of order n with a specified number of leaves or maximum degree or independence number or matching number.     

Perfect elimination orderings for symmetric matrices

We introduce a new class of structured symmetric matrices by extending the notion of perfect elimination ordering from graphs to weighted graphs or matrices. This offers a common framework capturing common vertex elimination orderings of monotone families of chordal graphs, Robinsonian matrices and ultrametrics. We give a structural characterization for matrices that admit perfect elimination orderings in terms of forbidden substructures generalizing chordless cycles in graphs.

     

Towards a spectral theory of graphs based on the signless Laplacian, II

A spectral graph theory is a theory in which graphs are studied by means of eigenvalues of a matrix M which is in a prescribed way defined for any graph. This theory is called M-theory. We outline a spectral theory of graphs based on the signless Laplacians Q and compare it with other spectral theories, in particular to those based on the adjacency matrix A and the Laplacian L. As demonstrated in the first part, the Q-theory can be constructed in part using various connections to other theories: equivalency with A-theory and L-theory for regular graphs, common features with L-theory for bipartite graphs, general analogies with A-theory and analogies with A-theory via line graphs and subdivision graphs. In this part, we introduce notions of enriched and restricted spectral theories and present results on integral graphs, enumeration of spanning trees, characterizations by eigenvalues, cospectral graphs and graph angles.     

Fence facets from non-regular graphs for the linear ordering polytope

We present a new class of facet defining inequalities for the linear ordering polytope. The underlying graphs of these new inequalities are non-regular (have vertices of different degrees); the other known classes of fence inequalities are induced by regular graphs.     

The (signless) Laplacian spectral radius of unicyclic and bicyclic graphs with <Emphasis Type="Italic">n</Emphasis> vertices and <Emphasis Type="Italic">k</Emphasis> pendant vertices

In this paper, the effects on the signless Laplacian spectral radius of a graph are studied when some operations, such as edge moving, edge subdividing, are applied to the graph. Moreover, the largest signless Laplacian spectral radius among the all unicyclic graphs with n vertices and k pendant vertices is identified. Furthermore, we determine the graphs with the largest Laplacian spectral radii among the all unicyclic graphs and bicyclic graphs with n vertices and k pendant vertices, respectively.     

Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number

Asteroidal Triple‐free (AT‐free) graphs have received considerable attention due to their inclusion of various important graphs families, such as interval and cocomparability graphs. The asteroidal number of a graph is the size of a largest subset of vertices such that the removal of the closed neighborhood of any vertex in the set leaves the remaining vertices of the set in the same connected component. (AT‐free graphs have asteroidal number at most 2.) In this article, we characterize graphs of bounded asteroidal number by means of a vertex elimination ordering, thereby solving a long‐standing open question in algorithmic graph theory. Similar characterizations are known for chordal, interval, and cocomparability graphs.     

On the spectral radius of bicyclic graphs with n vertices and diameter d

Bicyclic graphs are connected graphs in which the number of edges equals the number of vertices plus one. In this paper we determine the graph with the largest spectral radius among all bicyclic graphs with n vertices and diameter d. As an application, we give first three graphs among all bicyclic graphs on n vertices, ordered according to their spectral radii in decreasing order.     

On the Structure of Bull-Free Perfect Graphs, 2: the Weakly Chordal Case

 A bull is a graph obtained by adding a pendant vertex at two vertices of a triangle. A graph is perfectly orderable if it admits an ordering such that the greedy sequential method applied on this ordering produces an optimal coloring for every induced subgraph. Chvátal conjectured that every bull-free graph with no odd hole or antihole is perfectly orderable. In a previous paper we studied the structure of general bull-free perfect graphs, and reduced Chvátal's conjecture to the case of weakly chordal graphs. Here we focus on weakly chordal graphs, and we reduce Chvátal's conjecture to a restricted case. Our method lays out the structure of all bull-free weakly chordal graphs. These results have been used recently by Hayward to establish Chvátal's conjecture for this restricted case and therefore in full. Received: November 26, 1997?Final version received: February 27, 2001     

On well quasi-order of graph classes under homomorphic image orderings

In this paper we consider the question of well quasi-order for classes defined by a single obstruction within the classes of all graphs, digraphs and tournaments, under the homomorphic image ordering (in both its standard and strong forms). The homomorphic image ordering was introduced by the authors in a previous paper and corresponds to the existence of a surjective homomorphism between two structures. We obtain complete characterisations in all cases except for graphs under the strong ordering, where some open questions remain.     

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.