The Laplacian spread of graphs

The Laplacian spread of a graph is defined as the difference between the largest and second smallest eigenvalues of the Laplacian matrix of the graph. In this paper, bounds are obtained for the Laplacian spread of graphs. By the Laplacian spread, several upper bounds of the Nordhaus-Gaddum type of Laplacian eigenvalues are improved. Some operations on Laplacian spread are presented. Connected c-cyclic graphs with n vertices and Laplacian spread n − 1 are discussed.     

The theorem on planar graphs

In the late 1920s several mathematicians were on the verge of discovering a theorem for characterizing planar graphs. The proof of such a theorem was published in 1930 by Kazimierz Kuratowski, and soon thereafter the theorem was referred to as the Kuratowski Theorem. It has since become the most frequently cited result in graph theory. Recently, the name of Pontryagin has been coupled with that of Kuratowski when identifying this result. The events related to this development are examined with the object of determining to whom and in what proportion the credit should be given for the discovery of this theorem.     

Elliptic operators on planar graphs: Unique continuation for eigenfunctions and nonpositive curvature

This paper is concerned with elliptic operators on plane tessellations. We show that such an operator does not admit a compactly supported eigenfunction if the combinatorial curvature of the tessellation is nonpositive. Furthermore, we show that the only geometrically finite, repetitive plane tessellations with nonpositive curvature are the regular and tilings.

     

The Laplacian incidence energy of graphs

The Laplacian incidence energy of a graph is defined as the sum of the singular values of its normalized oriented incidence matrix. In this paper, we give sharp upper and lower bounds as well as the Coulson integral formula for the Laplacian incidence energy. Moreover, we show a close relation of the Laplacian incidence energy, normalized incidence energy and Randi? energy.     

The Laplacian spectral radius of graphs

The Laplacian spectral radius of a graph is the largest eigenvalue of the associated Laplacian matrix. In this paper, we improve Shi’s upper bound for the Laplacian spectral radius of irregular graphs and present some new bounds for the Laplacian spectral radius of some classes of graphs.     

The Laplacian energy of random graphs

Gutman et al. introduced the concepts of energy E(G) and Laplacian energy EL(G) for a simple graph G, and furthermore, they proposed a conjecture that for every graph G, E(G) is not more than EL(G). Unfortunately, the conjecture turns out to be incorrect since Liu et al. and Stevanovi? et al. constructed counterexamples. However, So et al. verified the conjecture for bipartite graphs. In the present paper, we obtain, for a random graph, the lower and upper bounds of the Laplacian energy, and show that the conjecture is true for almost all graphs.     

The Laplacian spread of unicyclic graphs

The Laplacian spread of a graph is defined to be the difference between the largest eigenvalue and the second-smallest eigenvalue of the Laplacian matrix of the graph. In a recent work the trees with maximal Laplacian spread and with minimal Laplacian spread among all trees of fixed order are separately determined. In this work, we characterize the unique unicyclic graph with maximal Laplacian spread among all connected unicyclic graphs of fixed order.     

The Laplacian spread of quasi-tree graphs

The Laplacian spread of a graph is defined to be the difference between the largest eigenvalue and the second-smallest eigenvalue of the Laplacian matrix of the graph. Bao, Tan and Fan [Y.H. Bao, Y.Y. Tan,Y.Z. Fan, The Laplacian spread of unicyclic graphs, Appl. Math. Lett. 22 (2009) 1011-1015.] characterize the unique unicyclic graph with maximum Laplacian spread among all connected unicyclic graphs of fixed order. In this paper, we characterize the unique quasi-tree graph with maximum Laplacian spread among all quasi-tree graphs in the set Q(n,d) with .     

The Laplacian spectral radius of graphs on surfaces

Let G be an n-vertex (n?3) simple graph embeddable on a surface of Euler genus γ (the number of crosscaps plus twice the number of handles). Denote by Δ the maximum degree of G. In this paper, we first present two upper bounds on the Laplacian spectral radius of G as follows:

(i)

     

Constructably Laplacian integral graphs

A graph is Laplacian integral if the spectrum of its Laplacian matrix consists entirely of integers. We consider the class of constructably Laplacian integral graphs - those graphs that be constructed from an empty graph by adding a sequence of edges in such a way that each time a new edge is added, the resulting graph is Laplacian integral. We characterize the constructably Laplacian integral graphs in terms of certain forbidden vertex-induced subgraphs, and consider the number of nonisomorphic Laplacian integral graphs that can be constructed by adding a suitable edge to a constructably Laplacian integral graph. We also discuss the eigenvalues of constructably Laplacian integral graphs, and identify families of isospectral nonisomorphic graphs within the class.     

The minimum Laplacian spread of unicyclic graphs

The Laplacian spread of a graph [1] is defined as the difference between the largest eigenvalue and the second-smallest eigenvalue of the associated Laplacian matrix. In this paper, the minimum Laplacian spread of unicyclic graphs with given order is determined.     

The Laplacian polynomial and Kirchhoff index of graphs derived from regular graphs

Let R(G)$R\left(G\right)$ be the graph obtained from G$G$ by adding a new vertex corresponding to each edge of G$G$ and by joining each new vertex to the end vertices of the corresponding edge, and Q(G)$Q\left(G\right)$ be the graph obtained from G$G$ by inserting a new vertex into every edge of G$G$ and by joining by edges those pairs of these new vertices which lie on adjacent edges of G$G$. In this paper, we determine the Laplacian polynomials of R(G)$R\left(G\right)$ and Q(G)$Q\left(G\right)$ of a regular graph G$G$; on the other hand, we derive formulae and lower bounds of the Kirchhoff index of these graphs.     

The uniquely embeddable planar graphs

Whitney [7] proved in 1932 that for any two embeddings of a planar 3-connected graph, their combinatorial duals are isomorphic. In this manner, the term “uniquely embeddable planar graph” was introduced. It is a well-known fact that combinatorial and geometrical duals are equivalent concepts. In this paper, the concept of unique embeddability is introduced in terms of special types of isomorphisms between any two embeddings of a planar graph. From this, the class U of all graphs which are uniquely embeddable in the plane according to this definition, is determined, and the planar 3-connected graphs are a proper subset of U. It turns out that the graphs in U have a unique geometrical dual (i.e., for any two embeddings of such a graph, their geometrical duals are isomorphic). Furthermore, the theorems and their proofs do not involve any type of duals.     

Joint seminormality and Dirac operators

In this article, an approach to joint seminormality based on the theory of Dirac and Laplace operators on Dirac vector bundles is presented. To eachn-tuple of bounded linear operators on a complex Hilbert space we first associate a Dirac bundle furnished with a metric-preserving linear connection defined in terms of thatn-tuple. Employing standard spin geometry techniques we next get a Bochner type and two Bochner-Kodaira type identities in multivariable operator theory. Further, four different classes of jointly seminormal tuples are introduced by imposing semidefiniteness conditions on the remainders in the corresponding Bochner-Kodaira identities. Thus we create a setting in which the classical Bochner's method can be put into action. In effect, we derive some vanishing theorems regarding various spectral sets associated with commuting tuples. In the last part of this article we investigate a rather general concept of seminormality for self-adjoint tuples with an even or odd number of entries.     

Convex drawings of hierarchical planar graphs and clustered planar graphs

In this paper, we present results on convex drawings of hierarchical graphs and clustered graphs. A convex drawing is a planar straight-line drawing of a plane graph, where every facial cycle is drawn as a convex polygon. Hierarchical graphs and clustered graphs are useful graph models with structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures.We first present the necessary and sufficient conditions for a hierarchical plane graph to admit a convex drawing. More specifically, we show that the necessary and sufficient conditions for a biconnected plane graph due to Thomassen [C. Thomassen, Plane representations of graphs, in: J.A. Bondy, U.S.R. Murty (Eds.), Progress in Graph Theory, Academic Press, 1984, pp. 43–69] remains valid for the case of a hierarchical plane graph. We then prove that every internally triconnected clustered plane graph with a completely connected clustering structure admits a “fully convex drawing,” a planar straight-line drawing such that both clusters and facial cycles are drawn as convex polygons. We also present algorithms to construct such convex drawings of hierarchical graphs and clustered graphs.     

The Laplacian spectral radius of some bipartite graphs

In this paper, we study the largest Laplacian spectral radius of the bipartite graphs with n vertices and k cut edges and the bicyclic bipartite graphs, respectively. Identifying the center of a star K_1,k and one vertex of degree n of K_m,n, we denote by the resulting graph. We show that the graph (1?k?n-4) is the unique graph with the largest Laplacian spectral radius among the bipartite graphs with n vertices and k cut edges, and (n?7) is the unique graph with the largest Laplacian spectral radius among all the bicyclic bipartite graphs.