On the signless Laplacian spectral characterization of the line graphs of T-shape trees

A graph is determined by its signless Laplacian spectrum if no other nonisomorphic graph has the same signless Laplacian spectrum (simply G is DQS). Let T (a, b, c) denote the T-shape tree obtained by identifying the end vertices of three paths P _a+2, P _b+2 and P _c+2. We prove that its all line graphs L(T(a, b, c)) except L(T(t, t, 2t+1)) (t ? 1) are DQS, and determine the graphs which have the same signless Laplacian spectrum as L(T(t, t, 2t + 1)). Let µ₁(G) be the maximum signless Laplacian eigenvalue of the graph G. We give the limit of µ₁(L(T(a, b, c))), too.     

On a signless Laplacian spectral characterization of -shape trees

Let M be an associated matrix of a graph G (the adjacency, Laplacian and signless Laplacian matrix). Two graphs are said to be cospectral with respect to M if they have the same M spectrum. A graph is said to be determined by M spectrum if there is no other non-isomorphic graph with the same spectrum with respect to M. It is shown that T-shape trees are determined by their Laplacian spectra. Moreover among them those are determined by their adjacency spectra are characterized. In this paper, we identify graphs which are cospectral to a given T-shape tree with respect to the signless Laplacian matrix. Subsequently, T-shape trees which are determined by their signless Laplacian spectra are identified.     

The signless Laplacian spectral radius of tricyclic graphs and trees with k pendant vertices

In this paper, we consider the following problem: of all tricyclic graphs or trees of order n with k pendant vertices (n,k fixed), which achieves the maximal signless Laplacian spectral radius?We determine the graph with the largest signless Laplacian spectral radius among all tricyclic graphs with n vertices and k pendant vertices. Then we show that the maximal signless Laplacian spectral radius among all trees of order n with k pendant vertices is obtained uniquely at T_n,k, where T_n,k is a tree obtained from a star K_1,k and k paths of almost equal lengths by joining each pendant vertex to one end-vertex of one path. We also discuss the signless Laplacian spectral radius of T_n,k and give some results.     

A note on the spectral characterization of dumbbell graphs

The dumbbell graph, denoted by D_a,b,c, is a bicyclic graph consisting of two vertex-disjoint cycles C_a and C_b joined by a path P_c+3 (c-1) having only its end-vertices in common with the two cycles. By using a new cospectral invariant for (r,r+1)-almost regular graphs, we will show that almost all dumbbell graphs (without cycle C₄ as a subgraph) are determined by the adjacency spectrum.     

Connected graphs with maximal Q-index: The one-dominating-vertex case

By the signless Laplacian of a (simple) graph G we mean the matrix Q(G)=D(G)+A(G), where A(G),D(G) denote respectively the adjacency matrix and the diagonal matrix of vertex degrees of G. For every pair of positive integers n,k, it is proved that if 3?k?n-3, then H_n,k, the graph obtained from the star K_1,n-1 by joining a vertex of degree 1 to k+1 other vertices of degree 1, is the unique connected graph that maximizes the largest signless Laplacian eigenvalue over all connected graphs with n vertices and n+k edges.     

Signless Laplacian spectral characterization of 4-rose graphs

A rose graph with p petals (or p-rose graph) is a graph obtained by taking p cycles with just a vertex in common. In this paper, we prove that all 4-rose graphs are determined by their signless Laplacian spectra.     

On the reduced signless Laplacian spectrum of a degree maximal graph

For a (simple) graph G, the signless Laplacian of G is the matrix A(G)+D(G), where A(G) is the adjacency matrix and D(G) is the diagonal matrix of vertex degrees of G; the reduced signless Laplacian of G is the matrix Δ(G)+B(G), where B(G) is the reduced adjacency matrix of G and Δ(G) is the diagonal matrix whose diagonal entries are the common degrees for vertices belonging to the same neighborhood equivalence class of G. A graph is said to be (degree) maximal if it is connected and its degree sequence is not majorized by the degree sequence of any other connected graph. For a maximal graph, we obtain a formula for the characteristic polynomial of its reduced signless Laplacian and use the formula to derive a localization result for its reduced signless Laplacian eigenvalues, and to compare the signless Laplacian spectral radii of two well-known maximal graphs. We also obtain a necessary condition for a maximal graph to have maximal signless Laplacian spectral radius among all connected graphs with given numbers of vertices and edges.     

On the signless Laplacian index of cacti with a given number of pendant vertices

A connected graph G is a cactus if any two of its cycles have at most one common vertex. In this article, we determine graphs with the largest signless Laplacian index among all the cacti with n vertices and k pendant vertices. As a consequence, we determine the graph with the largest signless Laplacian index among all the cacti with n vertices; we also characterize the n-vertex cacti with a perfect matching having the largest signless Laplacian index.     

Bounds for the signless Laplacian energy

The energy of a graph G is the sum of the absolute values of the eigenvalues of the adjacency matrix of G. The Laplacian (respectively, the signless Laplacian) energy of G is the sum of the absolute values of the differences between the eigenvalues of the Laplacian (respectively, signless Laplacian) matrix and the arithmetic mean of the vertex degrees of the graph. In this paper, among some results which relate these energies, we point out some bounds to them using the energy of the line graph of G. Most of these bounds are valid for both energies, Laplacian and signless Laplacian. However, we present two new upper bounds on the signless Laplacian which are not upper bounds for the Laplacian energy.     

Laplacian coefficients of trees with given number of leaves or vertices of degree two

Let G be a simple undirected n-vertex graph with the characteristic polynomial of its Laplacian matrix . It is well known that for trees the Laplacian coefficient c_n-2 is equal to the Wiener index of G, while c_n-3 is equal to the modified hyper-Wiener index of graph. Using a result of Zhou and Gutman on the relation between the Laplacian coefficients and the matching numbers in subdivided bipartite graphs, we characterize the trees with k leaves (pendent vertices) which simultaneously minimize all Laplacian coefficients. In particular, this extremal balanced starlike tree S(n,k) minimizes the Wiener index, the modified hyper-Wiener index and recently introduced Laplacian-like energy. We prove that graph S(n,n-1-p) has minimal Laplacian coefficients among n-vertex trees with p vertices of degree two. In conclusion, we illustrate on examples of these spectrum-based invariants that the opposite problem of simultaneously maximizing all Laplacian coefficients has no solution, and pose a conjecture on extremal unicyclic graphs with k leaves.     

拟树图按第二大无符号拉普拉斯特征值排序

A connected graph G=(V,E) is called a quasi-tree graph if there exists a vertex v_0∈V(G) such that G-v_0 is a tree.In this paper,we determine all quasi-tree graphs of order n with the second largest signless Laplacian eigenvalue greater than or equal to n-3.As an application,we determine all quasi-tree graphs of order n with the sum of the two largest signless Laplacian eigenvalues greater than to 2 n-5/4.     

The lollipop graph is determined by its Q-spectrum

A graph G is said to be determined by its Q-spectrum if with respect to the signless Laplacian matrix Q, any graph having the same spectrum as G is isomorphic to G. The lollipop graph, denoted by H_n,p, is obtained by appending a cycle C_p to a pendant vertex of a path P_n−p. In this paper, it is proved that all lollipop graphs are determined by their Q-spectra.     

The least eigenvalue of signless Laplacian of graphs under perturbation

We investigate how the least eigenvalue of the signless Laplacian of a graph changes by relocating a bipartite branch from one vertex to another vertex, and minimize the least eigenvalue of the signless Laplacian among the class of connected graphs with fixed order which contains a given non-bipartite graph as an induced subgraph.     

On the maximal energy tree with two maximum degree vertices

For a simple graph G, the energy E(G) is defined as the sum of the absolute values of all eigenvalues of its adjacent matrix.For Δ?3 and t?3, denote by T_a(Δ,t) (or simply T_a) the tree formed from a path P_t on t vertices by attaching Δ-1P₂’s on each end of the path P_t, and T_b(Δ,t) (or simply T_b) the tree formed from P_t+2 by attaching Δ-1P₂’s on an end of the P_t+2 and Δ-2P₂’s on the vertex next to the end.In Li et al.(2009) [16] proved that among trees of order n with two vertices of maximum degree Δ, the maximal energy tree is either the graph T_a or the graph T_b, where t=n+4-4Δ?3.However, they could not determine which one of T_a and T_b is the maximal energy tree.This is because the quasi-order method is invalid for comparing their energies.In this paper, we use a new method to determine the maximal energy tree.It turns out that things are more complicated.We prove that the maximal energy tree is T_b for Δ?7 and any t?3, while the maximal energy tree is T_a for Δ=3 and any t?3.Moreover, for Δ=4, the maximal energy tree is T_a for all t?3 but one exception that t=4, for which T_b is the maximal energy tree.For Δ=5, the maximal energy tree is T_b for all t?3 but 44 exceptions that t is both odd and 3?t?89, for which T_a is the maximal energy tree.For Δ=6, the maximal energy tree is T_b for all t?3 but three exceptions that t=3,5,7, for which T_a is the maximal energy tree.One can see that for most cases of Δ, T_b is the maximal energy tree,Δ=5 is a turning point, and Δ=3 and 4 are exceptional cases, which means that for all chemical trees (whose maximum degrees are at most 4) with two vertices of maximum degree at least 3, T_a has maximal energy, with only one exception T_a(4,4).     

图的无符号拉普拉斯和距离无符号拉普拉斯特征值

Let G be a simple graph. We first show that ■, where δiand di denote the i-th signless Laplacian eigenvalue and the i-th degree of vertex in G, respectively.Suppose G is a simple and connected graph, then some inequalities on the distance signless Laplacian eigenvalues are obtained by deleting some vertices and some edges from G. In addition, for the distance signless Laplacian spectral radius ρQ(G), we determine the extremal graphs with the minimum ρQ(G) among the trees with given diameter, the unicyclic and bicyclic graphs with given girth, respectively.     

The signless Laplacian spectra of the corona and edge corona of two graphs

We give complete information about the signless Laplacian spectrum of the corona of a graph G ₁ and a regular graph G ₂, and complete information about the signless Laplacian spectrum of the edge corona of a connected regular graph G ₁ and a regular graph G ₂.     

Distance signless Laplacian spectral radius and Hamiltonian properties of graphs

In this paper, we establish a sufficient condition on distance signless Laplacian spectral radius for a bipartite graph to be Hamiltonian. We also give two sufficient conditions on distance signless Laplacian spectral radius for a graph to be Hamilton-connected and traceable from every vertex, respectively. Furthermore, we obtain a sufficient condition for a graph to be Hamiltonian in terms of the distance signless Laplacian spectral radius of the complement of a graph G.     

Embeddings of bipartite graphs

If G is a bipartite graph with bipartition A, B then let G_m,n(A, B) be obtained from G by replacing each vertex a of A by an independent set a₁, …, a_m, each vertex b of B by an independent set b₁,…, b_n, and each edge ab of G by the complete bipartite graph with edges a_ib_j (1 ≤ i ≤ m and 1 ≤ j ≤ n). Whenever G has certain types of spanning forests, then cellular embeddings of G in surfaces S may be lifted to embeddings of G_m,n(A, B) having faces of the same sizes as those of G in S. These results are proved by the technique of “excess-current graphs.” They include new genus embeddings for a large class of bipartite graphs.     

Energy of generalized line graphs

The energy of a graph is equal to the sum of the absolute values of its eigenvalues. Line graphs play an important role in the study of graph theory. Generalized line graphs extend the ideas of both line graphs and cocktail party graphs. In this paper, we establish relations between the energy of the generalized line graph of a graph G and the Laplacian and signless Laplacian energies of G. We give upper and lower bounds for the energy of generalized line graphs. Finally, we present upper and lower bounds for some special graphs.     

Algebraic Shifting of Finite Graphs

In the present article, for bipartite graphs and chordal graphs, their exterior algebraic shifted graph and their symmetric algebraic shifted graph are studied. First, we will determine the symmetric algebraic shifted graph of complete bipartite graphs. It turns out that for a ≥ 3 and b ≥ 3, the exterior algebraic shifted graph of the complete bipartite graph K _a,b of size a, b is different from the symmetric algebraic shifted graph of K _a,b . Second, we will show that the exterior algebraic shifted graph of any chordal graph G coincides with the symmetric algebraic shifted graph of G. In addition, it will be shown that the exterior algebraic shifted graph of any chordal graph G is equal to some combinatorial shifted graph of G.