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.     

Bounds on the eigenvalues of graphs with cut vertices or edges

In this paper, we characterize the extremal graph having the maximal Laplacian spectral radius among the connected bipartite graphs with n vertices and k cut vertices, and describe the extremal graph having the minimal least eigenvalue of the adjacency matrices of all the connected graphs with n vertices and k cut edges. We also present lower bounds on the least eigenvalue in terms of the number of cut vertices or cut edges and upper bounds on the Laplacian spectral radius in terms of the number of cut vertices.     

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.     

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.     

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.     

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.     

The smallest signless Laplacian spectral radius of graphs with a given clique number

The signless Laplacian spectral radius of a graph G is the largest eigenvalue of its signless Laplacian matrix. In this paper, the first four smallest values of the signless Laplacian spectral radius among all connected graphs with maximum clique of size greater than or equal to 2 are obtained.     

Theorems on partitioned matrices revisited and their applications to graph spectra

Some old results about spectra of partitioned matrices due to Goddard and Schneider or Haynsworth are re-proved. A new result is given for the spectrum of a block-stochastic matrix with the property that each off-diagonal block has equal entries and each diagonal block has equal diagonal entries and equal off-diagonal entries. The result is applied to the study of the spectra of the usual graph matrices by partitioning the vertex set of the graph according to the neighborhood equivalence relation. The concept of a reduced graph matrix is introduced. The question of when n-2 is the second largest signless Laplacian eigenvalue of a connected graph of order n is treated. A recent conjecture posed by Tam, Fan and Zhou on graphs that maximize the signless Laplacian spectral radius over all (not necessarily connected) graphs with given numbers of vertices and edges is refuted. The Laplacian spectrum of a (degree) maximal graph is reconsidered.     

Unoriented Laplacian maximizing graphs are degree maximal

A connected graph is said to be unoriented Laplacian maximizing if the spectral radius of its unoriented Laplacian matrix attains the maximum among all connected graphs with the same number of vertices and the same number of edges. A graph is said to be threshold (maximal) if its degree sequence is not majorized by the degree sequence of any other graph (and, in addition, the graph is connected). It is proved that an unoriented Laplacian maximizing graph is maximal and also that there are precisely two unoriented Laplacian maximizing graphs of a given order and with nullity 3. Our treatment depends on the following known characterization: a graph G is threshold (maximal) if and only if for every pair of vertices u,v of G, the sets N(u)?{v},N(v)?{u}, where N(u) denotes the neighbor set of u in G, are comparable with respect to the inclusion relation (and, in addition, the graph is connected). A conjecture about graphs that maximize the unoriented Laplacian matrix among all graphs with the same number of vertices and the same number of edges is also posed.     

Graphs with maximal signless Laplacian spectral radius

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. It is known that connected graphs G that maximize the signless Laplacian spectral radius ρ(Q(G)) over all connected graphs with given numbers of vertices and edges are (degree) maximal. For a maximal graph G with n vertices and r distinct vertex degrees δ_r>δ_r-1>?>δ₁, it is proved that ρ(Q(G))<ρ(Q(H)) for some maximal graph H with n+1 (respectively, n) vertices and the same number of edges as G if either G has precisely two dominating vertices or there exists an integer such that δ_i+δ_r+1-i?n+1 (respectively, δ_i+δ_r+1-i?δ_l+δ_r-l+1). Graphs that maximize ρ(Q(G)) over the class of graphs with m edges and m-k vertices, for k=0,1,2,3, are completely determined.     

The signless Laplacian spectral radius of bicyclic graphs with prescribed degree sequences

In this paper, we characterize all extremal connected bicyclic graphs with the largest signless Laplacian spectral radius in the set of all connected bicyclic graphs with prescribed degree sequences. Moreover, the signless Laplacian majorization theorem is proved to be true for connected bicyclic graphs. As corollaries, all extremal connected bicyclic graphs having the largest signless Laplacian spectral radius are obtained in the set of all connected bicyclic graphs of order n (resp. all connected bicyclic graphs with a specified number of pendant vertices, and all connected bicyclic graphs with given maximum degree).     

Some results on Laplacian spectral radius of graphs with cut vertices

In this paper, we give some results on Laplacian spectral radius of graphs with cut vertices, and as their applications, we also determine the unique graph with the largest Laplacian spectral radius among all unicyclic graphs with n vertices and diameter d, 3?d?n−3.     

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.     

On the signless Laplacian index of unicyclic graphs with fixed diameter

In the paper, we identify graphs with the maximal signless Laplacian spectral radius among all the unicyclicgraphs with n vertices of diameter d.     

Some graft transformations and its applications on the distance spectral radius of a graph

Let D(G)=(d_i,j)_n×n denote the distance matrix of a connected graph G with order n, where d_ij is equal to the distance between v_i and v_j in G. The largest eigenvalue of D(G) is called the distance spectral radius of graph G, denoted by ?(G). In this paper, some graft transformations that decrease or increase ?(G) are given. With them, for the graphs with both order n and k pendant vertices, the extremal graphs with the minimum distance spectral radius are completely characterized; the extremal graph with the maximum distance spectral radius is shown to be a dumbbell graph (obtained by attaching some pendant edges to each pendant vertex of a path respectively) when 2≤k≤n−2; for k=1,2,3,n−1, the extremal graphs with the maximum distance spectral radius are completely characterized.     

Graphs with given number of cut vertices and extremal Merrifield-Simmons index

The Merrifield-Simmons index of a graph is defined as the total number of its independent sets, including the empty set. Denote by G(n,k) the set of connected graphs with n vertices and k cut vertices. In this paper, we characterize the graphs with the maximum and minimum Merrifield-Simmons index, respectively, among all graphs in G(n,k) for all possible k values.     

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.     

Quotient of spectral radius, (signless) Laplacian spectral radius and clique number of graphs

In this paper, the upper and lower bounds for the quotient of spectral radius (Laplacian spectral radius, signless Laplacian spectral radius) and the clique number together with the corresponding extremal graphs in the class of connected graphs with n vertices and clique number ω(2 ≤ ω ≤ n) are determined. As a consequence of our results, two conjectures given in Aouchiche (2006) and Hansen (2010) are proved.     

Edge fault tolerance analysis of super k-restricted connected networks

An edge cut X of a connected graph G is a k-restricted edge cut if G-X is disconnected and every component of G-X has at least k vertices. Additionally, if the deletion of a minimum k-restricted edge cut isolates a connected component of k vertices, then the graph is said to be super-λ_k. In this paper, several sufficient conditions yielding super-λ_k graphs are given in terms of the girth and the diameter.