On the Szeged and the Laplacian Szeged spectrum of a graph

For a given graph G its Szeged weighting is defined by w(e)=n_u(e)n_v(e), where e=uv is an edge of G,n_u(e) is the number of vertices of G closer to u than to v, and n_v(e) is defined analogously. The adjacency matrix of a graph weighted in this way is called its Szeged matrix. In this paper we determine the spectra of Szeged matrices and their Laplacians for several families of graphs. We also present sharp upper and lower bounds on the eigenvalues of Szeged matrices of graphs.     

The asymptotic behaviour of the heat equation in a twisted Dirichlet-Neumann waveguide

We consider the heat equation in a straight strip, subject to a combination of Dirichlet and Neumann boundary conditions. We show that a switch of the respective boundary conditions leads to an improvement of the decay rate of the heat semigroup of the order of t−1/2. The proof employs similarity variables that lead to a non-autonomous parabolic equation in a thin strip contracting to the real line, that can be analysed on weighted Sobolev spaces in which the operators under consideration have discrete spectra. A careful analysis of its asymptotic behaviour shows that an added Dirichlet boundary condition emerges asymptotically at the switching point, breaking the real line in two half-lines, which leads asymptotically to the 1/2 gain on the spectral lower bound, and the t−1/2 gain on the decay rate in the original physical variables.This result is an adaptation to the case of strips with twisted boundary conditions of previous results by the authors on geometrically twisted Dirichlet tubes.     

On the critical ideals of graphs

We introduce some determinantal ideals of the generalized Laplacian matrix associated to a digraph G, that we call critical ideals of G. Critical ideals generalize the critical group and the characteristic polynomials of the adjacency and Laplacian matrices of a digraph. The main results of this article are the determination of some minimal generator sets and the reduced Gröbner basis for the critical ideals of the complete graphs, the cycles and the paths. Also, we establish a bound between the number of trivial critical ideals and the stability and clique numbers of a graph.     

Singular asymptotic expansions for Dirichlet eigenvalues and eigenfunctions of the Laplacian on thin planar domains

We consider the Laplace operator with Dirichlet boundary conditions on a planar domain and study the effect that performing a scaling in one direction has on the spectrum. We derive the asymptotic expansion for the eigenvalues and corresponding eigenfunctions as a function of the scaling parameter around zero. This method allows us, for instance, to obtain an approximation for the first Dirichlet eigenvalue for a large class of planar domains, under very mild assumptions.     

On the topology of graph picture spaces

We study the space of pictures of a graph G in complex projective d-space. The main result is that the homology groups (with integer coefficients) of are completely determined by the Tutte polynomial of G. One application is a criterion in terms of the Tutte polynomial for independence in the d-parallel matroids studied in combinatorial rigidity theory. For certain special graphs called orchards, the picture space is smooth and has the structure of an iterated projective bundle. We give a Borel presentation of the cohomology ring of the picture space of an orchard, and use this presentation to develop an analogue of the classical Schubert calculus.     

On the diameter and girth of a zero-divisor graph

For a commutative ring R with zero-divisors Z(R), the zero-divisor graph of R is Γ(R)=Z(R)−{0}, with distinct vertices x and y adjacent if and only if xy=0. In this paper, we characterize when either or . We then use these results to investigate the diameter and girth for the zero-divisor graphs of polynomial rings, power series rings, and idealizations.     

The subconstituent algebra of a bipartite distance-regular graph; thin modules with endpoint two

We consider a bipartite distance-regular graph Γ with diameter D?4, valency k?3, intersection numbers b_i,c_i, distance matrices A_i, and eigenvalues θ₀>θ₁>?>θ_D. Let X denote the vertex set of Γ and fix x∈X. Let T=T(x) denote the subalgebra of Mat_X(C) generated by , where A=A₁ and denotes the projection onto the ith subconstituent of Γ with respect to x. T is called the subconstituent algebra (or Terwilliger algebra) of Γ with respect to x. An irreducible T-module W is said to be thin whenever for 0?i?D. By the endpoint of W we mean . Assume W is thin with endpoint 2. Observe is a one-dimensional eigenspace for ; let η denote the corresponding eigenvalue. It is known where , and d=⌊D/2⌋. To describe the structure of W we distinguish four cases: (i) ; (ii) D is odd and ; (iii) D is even and ; (iv) . We investigated cases (i), (ii) in MacLean and Terwilliger [Taut distance-regular graphs and the subconstituent algebra, Discrete Math. 306 (2006) 1694-1721]. Here we investigate cases (iii), (iv) and obtain the following results. We show the dimension of W is D-1-e where e=1 in case (iii) and e=0 in case (iv). Let v denote a nonzero vector in . We show W has a basis , where E_i denotes the primitive idempotent of A associated with θ_i and where the set S is {1,2,…,d-1}∪{d+1,d+2,…,D-1} in case (iii) and {1,2,…,D-1} in case (iv). We show this basis is orthogonal (with respect to the Hermitian dot product) and we compute the square-norm of each basis vector. We show W has a basis , and we find the matrix representing A with respect to this basis. We show this basis is orthogonal and we compute the square-norm of each basis vector. We find the transition matrix relating our two bases for W.     

On a combinatorial property of choice functions of finite sets

We consider choice functions k[X]→X, where X is a finite set and k[X] denotes the set of all k-subsets of X. We define a property of domination for such maps generalizing the classical case k=2 (tournaments) and prove the existence of a dominating element generalizing the existence of a 2-root (king) in the classical case.     

Connected graphs containing a given connected graph as a unique greatest common subgraph

Those connected graphsG are determined for which there exist nonisomorphic connected graphs of equal size containingG as a unique greatest common subgraph. Analogous results are also obtained for weakly connected and strongly connected digraphs, as well as for induced subgraphs and induced subdigraphs.This research was supported by a Western Michigan University faculty research fellowship.This research was supported in part by a Western Michigan University research assistantship from the Graduate College and the College of Arts and Sciences.     

On the roots of independence polynomials of almost all very well-covered graphs

If s_k denotes the number of stable sets of cardinality k in graph G, and α(G) is the size of a maximum stable set, then is the independence polynomial of G [I. Gutman, F. Harary, Generalizations of the matching polynomial, Utilitas Math. 24 (1983) 97-106]. A graph G is very well-covered [O. Favaron, Very well-covered graphs, Discrete Math. 42 (1982) 177-187] if it has no isolated vertices, its order equals 2α(G) and it is well-covered, i.e., all its maximal independent sets are of the same size [M.D. Plummer, Some covering concepts in graphs, J. Combin. Theory 8 (1970) 91-98]. For instance, appending a single pendant edge to each vertex of G yields a very well-covered graph, which we denote by G^*. Under certain conditions, any well-covered graph equals G^* for some G [A. Finbow, B. Hartnell, R.J. Nowakowski, A characterization of well-covered graphs of girth 5 or greater, J. Combin. Theory Ser B 57 (1993) 44-68].The root of the smallest modulus of the independence polynomial of any graph is real [J.I. Brown, K. Dilcher, R.J. Nowakowski, Roots of independence polynomials of well-covered graphs, J. Algebraic Combin. 11 (2000) 197-210]. The location of the roots of the independence polynomial in the complex plane, and the multiplicity of the root of the smallest modulus are investigated in a number of articles.In this paper we establish formulae connecting the coefficients of I(G;x) and I(G^*;x), which allow us to show that the number of roots of I(G;x) is equal to the number of roots of I(G^*;x) different from -1, which appears as a root of multiplicity α(G^*)-α(G) for I(G^*;x). We also prove that the real roots of I(G^*;x) are in [-1,-1/2α(G^*)), while for a general graph of order n we show that its roots lie in |z|>1/(2n-1).Hoede and Li [Clique polynomials and independent set polynomials of graphs, Discrete Math. 125 (1994) 219-228] posed the problem of finding graphs that can be uniquely defined by their clique polynomials (clique-unique graphs). Stevanovic [Clique polynomials of threshold graphs, Univ. Beograd Publ. Elektrotehn. Fac., Ser. Mat. 8 (1997) 84-87] proved that threshold graphs are clique-unique. Here, we demonstrate that the independence polynomial distinguishes well-covered spiders among well-covered trees.     

Semiregular trees with minimal Laplacian spectral radius

A semiregular tree is a tree where all non-pendant vertices have the same degree. Among all semiregular trees with fixed order and degree, a graph with minimal (adjacency/Laplacian) spectral radius is a caterpillar. Counter examples show that the result cannot be generalized to the class of trees with a given (non-constant) degree sequence.     

Commute times for a directed graph using an asymmetric Laplacian

The expected commute times for a strongly connected directed graph are related to an asymmetric Laplacian matrix as a direct extension to similar well known formulas for undirected graphs. We show the close relationships between the asymmetric Laplacian and the so-called Fundamental matrix. We give bounds for the commute times in terms of the stationary probabilities for a random walk over the graph together with the asymmetric Laplacian and show how this can be approximated by a symmetrized Laplacian derived from a related weighted undirected graph.     

On the spectral radii and the signless Laplacian spectral radii of c-cyclic graphs with fixed maximum degree

If G is a connected undirected simple graph on n vertices and n+c-1 edges, then G is called a c-cyclic graph. Specially, G is called a tricyclic graph if c=3. Let Δ(G) be the maximum degree of G. In this paper, we determine the structural characterizations of the c-cyclic graphs, which have the maximum spectral radii (resp. signless Laplacian spectral radii) in the class of c-cyclic graphs on n vertices with fixed maximum degree . Moreover, we prove that the spectral radius of a tricyclic graph G strictly increases with its maximum degree when , and identify the first six largest spectral radii and the corresponding graphs in the class of tricyclic graphs on n vertices.     

Approximation of o-minimal maps satisfying a Lipschitz condition

Consider an o-minimal expansion of the real field. We show that definable Lipschitz continuous maps can be definably fine approximated by definable continuously differentiable Lipschitz maps whose Lipschitz constant is close to that of the original map.     

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.     

The disconnection number of a graph

The disconnection number d(X) is the least number of points in a connected topological graph X such that removal of d(X) points will disconnect X (Nadler, 1993 [6]). Let Dn denote the set of all homeomorphism classes of topological graphs with disconnection number n. The main result characterizes the members of Dn+1 in terms of four possible operations on members of Dn. In addition, if X and Y are topological graphs and X is a subspace of Y with no endpoints, then d(X)?d(Y) and Y obtains from X with exactly d(Y)−d(X) operations. Some upper and lower bounds on the size of Dn are discussed.The algorithm of the main result has been implemented to construct the classes Dn for n?8, to estimate the size of D₉, and to obtain information on certain subclasses such as non-planar graphs (n?9) and regular graphs (n?10).     

Plancherel-type estimates and sharp spectral multipliers

We study general spectral multiplier theorems for self-adjoint positive definite operators on L²(X,μ), where X is any open subset of a space of homogeneous type. We show that the sharp Hörmander-type spectral multiplier theorems follow from the appropriate estimates of the L² norm of the kernel of spectral multipliers and the Gaussian bounds for the corresponding heat kernel. The sharp Hörmander-type spectral multiplier theorems are motivated and connected with sharp estimates for the critical exponent for the Riesz means summability, which we also study here. We discuss several examples, which include sharp spectral multiplier theorems for a class of scattering operators on R³ and new spectral multiplier theorems for the Laguerre and Hermite expansions.     

Smoothing effects for classical solutions of the relativistic Landau-Maxwell system

The relativistic Landau-Maxwell system is one of the most fundamental and complete models for describing the dynamics of a dilute hot plasma in which particles interact through Coulomb collisions and their self-consistent electromagnetic field. In this work, we prove that the classical solutions obtained by Strain and Guo become immediately smooth with respect to all variable under the extra assumption of the electromagnetic field. As a by-product, we also prove that the classical solutions to the relativistic Landau-Poisson system and the relativistic Landau equation have the same property without any extra assumption.     

A sharp upper bound on the signless Laplacian spectral radius of graphs

Let G be a simple connected graph of order n   with degree sequence _d1,_d2,…,_dn$d_1,d_2,\dots ,d_n$ in non-increasing order. The signless Laplacian spectral radius ρ(Q(G))$\rho (Q(G))$ of G   is the largest eigenvalue of its signless Laplacian matrix Q(G)$Q(G)$. In this paper, we give a sharp upper bound on the signless Laplacian spectral radius ρ(Q(G))$\rho (Q(G))$ in terms of _di$d_i$, which improves and generalizes some known results.     

Global classical solutions to the initial value problem for the relativistic Landau equation

Global in time classical solutions near the relativistic Maxwellian are constructed for the relativistic Landau equation in the whole space. The construction of global solutions is based on refined energy analysis.