On the Laplacian Spectrum and Walk-regular Hypergraphs

We use the generalization of the Laplacian matrix to hypergraphs to obtain several spectral-like results on hypergraphs. For instance, we obtain upper bounds on the eccentricity and the excess of any vertex of hypergraphs. We extend to the case of hypergraphs the concepts of walk regularity and spectral regularity, showing that all walk-regular hypergraphs are spectrally-regular. Finally, we obtain an upper bound on the mean distance of walk-regular hypergraphs that involves all the Laplacian spectrum.     

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.     

Maximizing signless Laplacian or adjacency spectral radius of graphs subject to fixed connectivity

In this paper, we characterize the graphs with maximum signless Laplacian or adjacency spectral radius among all graphs with fixed order and given vertex or edge connectivity. We also discuss the minimum signless Laplacian or adjacency spectral radius of graphs subject to fixed connectivity. Consequently we give an upper bound of signless Laplacian or adjacency spectral radius of graphs in terms of connectivity. In addition we confirm a conjecture of Aouchiche and Hansen involving adjacency spectral radius and connectivity.     

Laplacian eigenvalues and partition problems in hypergraphs

We use the generalization of the Laplacian matrix to hypergraphs to obtain several spectral-like results on partition problems in hypergraphs which are computationally difficult to solve (NP-hard or NP-complete). Therefore it is very important to obtain nontrivial bounds. More precisely, the following parameters are bounded in the paper: bipartition width, averaged minimal cut, isoperimetric number, max-cut, independence number and domination number.     

超图的最优标号与特征值

研究超图的标号性质,首先利用拉普拉斯张量的第二小和最大特征值给出4一致超图的带宽和与割宽的上下界;其次构造与超图对应的简单图,通过其拉普拉斯矩阵的特征值给出超图带宽的下界.     

Spectral convergence and nonlinear dynamics of reaction-diffusion equations under perturbations of the domain

In this paper we obtain the continuity of attractors for semilinear parabolic problems with Neumann boundary conditions relatively to perturbations of the domain. We show that, if the perturbations on the domain are such that the convergence of eigenvalues and eigenfunctions of the Neumann Laplacian is granted then, we obtain the upper semicontinuity of the attractors. If, moreover, every equilibrium of the unperturbed problem is hyperbolic we also obtain the continuity of attractors. We also give necessary and sufficient conditions for the spectral convergence of Neumann problems under perturbations of the domain.     

Spectral radius of uniform hypergraphs and degree sequences

We present several upper bounds for the adjacency and signless Laplacian spectral radii of uniform hypergraphs in terms of degree sequences.     

Regularity and projective dimension of edge ideals

In this paper, we study the regularity and projective dimension of edge ideals. We provide two upper bounds for the regularity of edge ideals of vertex decomposable graphs in terms of the induced matching number and the number of cycles. Also, we generalize one of the upper bounds given by Dao and Schweig for the projective dimension of hypergraphs.     

The Laplacian spectral radii of trees with degree sequences

In this paper, we characterize all extremal trees with the largest Laplacian spectral radius in the set of all trees with a given degree sequence. Consequently, we also obtain all extremal trees with the largest Laplacian spectral radius in the sets of all trees of order n with the largest degree, the leaves number and the matching number, respectively.     

On point covers of multiple intervals and axis-parallel rectangles

In certain families of hypergraphs the transversal number is bounded by some function of the packing number. In this paper we study hypergraphs related to multiple intervals and axisparallel rectangles, respectively. Essential improvements of former established upper bounds are presented here. We explore the close connection between the two problems at issue.Supported by the Alexander von Humboldt Foundation and the NSF grant No. STC-91-19999Supported by the NSF grant No. CCR-92-00788, the (Hungarian) National Scientific Research Fund (OTKA) grant No. F014919. The author was visiting the Computation and Automation Institute, Budapest while part of this research was done.     

On perturbations of almost distance-regular graphs

In this paper we show that certain almost distance-regular graphs, the so-called h-punctually walk-regular graphs, can be characterized through the cospectrality of their perturbed graphs. A graph G with diameter D is called h-punctually walk-regular, for a given h≤D, if the number of paths of length ? between a pair of vertices u,v at distance h depends only on ?. The graph perturbations considered here are deleting a vertex, adding a loop, adding a pendant edge, adding/removing an edge, amalgamating vertices, and adding a bridging vertex. We show that for walk-regular graphs some of these operations are equivalent, in the sense that one perturbation produces cospectral graphs if and only if the others do. Our study is based on the theory of graph perturbations developed by Cvetkovi?, Godsil, McKay, Rowlinson, Schwenk, and others. As a consequence, some new characterizations of distance-regular graphs are obtained.     

一般超图的张量谱性质

将一致超图的逆Perron值的概念推广到了一般超图上,并证明了超图G连通的充要条件为其逆Perron值大于0。同时给出了一般超图G的二分宽度、等周数、离心率基于逆Perron值的一些下界。最后,讨论了张量的可奇染色问题,得到非负对称弱不可约张量A可奇染色的充要条件为A的拉普拉斯张量和无符号拉普拉斯张量有相同的的谱。     

On the sum of the Laplacian eigenvalues of a tree

Given an n-vertex graph G=(V,E), the Laplacian spectrum of G is the set of eigenvalues of the Laplacian matrix L=D-A, where D and A denote the diagonal matrix of vertex-degrees and the adjacency matrix of G, respectively. In this paper, we study the Laplacian spectrum of trees. More precisely, we find a new upper bound on the sum of the k largest Laplacian eigenvalues of every n-vertex tree, where k∈{1,…,n}. This result is used to establish that the n-vertex star has the highest Laplacian energy over all n-vertex trees, which answers affirmatively to a question raised by Radenkovi? and Gutman [10].     

Regularity of the sample paths of a class of second-order spde's

We study the sample path regularity of the solutions of a class of spde's which are second order in time and that includes the stochastic wave equation. Non-integer powers of the spatial Laplacian are allowed. The driving noise is white in time and spatially homogeneous. Continuing with the work initiated in Dalang and Mueller (Electron. J. Probab. 8 (2003) 1), we prove that the solutions belong to a fractional L²-Sobolev space. We also prove Hölder continuity in time and therefore, we obtain joint Hölder continuity in the time and space variables. Our conclusions rely on a precise analysis of the properties of the stochastic integral used in the rigourous formulation of the spde, as introduced by Dalang and Mueller. For spatial covariances given by Riesz kernels, we show that our results are optimal.     

A sharp upper bound on the maximal entry in the principal eigenvector of symmetric nonnegative matrix

An upper bound on the maximal entry in the principal eigenvector of a symmetric nonnegative matrix with zero diagonal entries is investigated in [S. Zhao, Y. Hong, On the bounds of maximal entries in the principal eigenvector of symmetric nonnegative matrix, Linear Algebra Appl. 340 (2002) 245-252]. We obtain a sharp upper bound on the maximal entry y^max_p in the principal eigenvector of symmetric nonnegative matrix in terms of order, the spectral radius, the largest and the smallest diagonal entries of that matrix. Our bound is applicable for any symmetric nonnegative matrix and the upper bound of Zhao and Hong (2002) for the maximal entry y^max_p follows as a special case. Moreover, we find an upper bound on maximal entry in the principal eigenvector for the signless Laplacian matrix of a graph.     

Improved bounds for the Laplacian energy of Bethe trees

For k, d?2, a Bethe tree is a rooted tree with k levels which the root vertex has degree d, the vertices from level 2 to k-1 have degree d+1 and the vertices at the level k are pendent vertices. So et al, using a theorem by Ky Fan have obtained both upper and lower bounds for the Laplacian energy of bipartite graphs. We shall employ the above mentioned theorem to obtain new and improved bounds for the Laplacian energy in the case of Bethe trees.     

On the Laplacian spectral radii of bipartite graphs

The Laplacian spectral radius of a graph is the largest eigenvalue of the associated Laplacian matrix. In this paper, we provide structural and behavioral details of graphs with maximum Laplacian spectral radius among all bipartite connected graphs of given order and size. Using these results, we provide a unified approach to determine the graphs with maximum Laplacian spectral radii among all trees, and all bipartite unicyclic, bicyclic, tricyclic and quasi-tree graphs, respectively.     

偶一致超图划分问题的若干结果

划分问题因其在多个领域的重要应用一直是图论的研究热点.利用张量的特征值研究超图的划分与奇划分,并结合边割的界给出最大奇割、平均最小割、等周数等超图拓扑指标的界.当k取2时,这些结果与对应的图谱理论中的经典结论一致,因此可视为这些结论在超图的推广.     

Monomial ideals, edge ideals of hypergraphs, and their graded Betti numbers

We use the correspondence between hypergraphs and their associated edge ideals to study the minimal graded free resolution of squarefree monomial ideals. The theme of this paper is to understand how the combinatorial structure of a hypergraph ℋ appears within the resolution of its edge ideal ℐ(ℋ). We discuss when recursive formulas to compute the graded Betti numbers of ℐ(ℋ) in terms of its sub-hypergraphs can be obtained; these results generalize our previous work (Hà, H.T., Van Tuyl, A. in J. Algebra 309:405–425, 2007) on the edge ideals of simple graphs. We introduce a class of hypergraphs, which we call properly-connected, that naturally generalizes simple graphs from the point of view that distances between intersecting edges are “well behaved.” For such a hypergraph ℋ (and thus, for any simple graph), we give a lower bound for the regularity of ℐ(ℋ) via combinatorial information describing ℋ and an upper bound for the regularity when ℋ=G is a simple graph. We also introduce triangulated hypergraphs that are properly-connected hypergraphs generalizing chordal graphs. When ℋ is a triangulated hypergraph, we explicitly compute the regularity of ℐ(ℋ) and show that the graded Betti numbers of ℐ(ℋ) are independent of the ground field. As a consequence, many known results about the graded Betti numbers of forests can now be extended to chordal graphs. Dedicated to Anthony V. Geramita on the occasion of his 65th birthday.