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 conjectures involving second largest signless Laplacian eigenvalue of graphs

Let G=(V,E) be a simple graph. Denote by D(G) the diagonal matrix of its vertex degrees and by A(G) its adjacency matrix. Then the Laplacian matrix of G is L(G)=D(G)-A(G) and the signless Laplacian matrix of G is Q(G)=D(G)+A(G). In this paper we obtain a lower bound on the second largest signless Laplacian eigenvalue and an upper bound on the smallest signless Laplacian eigenvalue of G. In [5], Cvetkovi? et al. have given a series of 30 conjectures on Laplacian eigenvalues and signless Laplacian eigenvalues of G (see also [1]). Here we prove five conjectures.     

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.     

Ordering of trees with fixed matching number by the Laplacian coefficients

Let G be a simple undirected graph with the characteristic polynomial of its Laplacian matrix L(G), . Aleksandar Ili? [A. Ili?, Trees with minimal Laplacian coefficients, Comput. Math. Appl. 59 (2010) 2776-2783] identified n-vertex trees with given matching number q which simultaneously minimize all Laplacian coefficients. In this paper, we give another proof of this result. Generalizing the approach in the above paper, we determine n-vertex trees with given matching number q which have the second minimal Laplacian coefficients. We also identify the n-vertex trees with a perfect matching having the largest and the second largest Laplacian coefficients, respectively. Extremal values on some indices, such as Wiener index, modified hyper-Wiener index, Laplacian-like energy, incidence energy, of n-vertex trees with matching number q are obtained in this paper.     

On the Estrada and Laplacian Estrada indices of graphs

The Estrada index of a graph G is defined as , where λ₁,λ₂,…,λ_n are the eigenvalues of G. The Laplacian Estrada index of a graph G is defined as , where μ₁,μ₂,…,μ_n are the Laplacian eigenvalues of G. An edge grafting operation on a graph moves a pendent edge between two pendent paths. We study the change of Estrada index of graph under edge grafting operation between two pendent paths at two adjacent vertices. As the application, we give the result on the change of Laplacian Estrada index of bipartite graph under edge grafting operation between two pendent paths at the same vertex. We also determine the unique tree with minimum Laplacian Estrada index among the set of trees with given maximum degree, and the unique trees with maximum Laplacian Estrada indices among the set of trees with given diameter, number of pendent vertices, matching number, independence number and domination number, respectively.     

Universal adjacency matrices with two eigenvalues

Consider a graph Γ on n vertices with adjacency matrix A and degree sequence (d₁,…,d_n). A universal adjacency matrix of Γ is any matrix in Span {A,D,I,J} with a nonzero coefficient for A, where and I and J are the n×n identity and all-ones matrix, respectively. Thus a universal adjacency matrix is a common generalization of the adjacency, the Laplacian, the signless Laplacian and the Seidel matrix. We investigate graphs for which some universal adjacency matrix has just two eigenvalues. The regular ones are strongly regular, complete or empty, but several other interesting classes occur.     

On the nullity of graphs with pendent vertices

The nullity of a graph G, denoted by η(G), is the multiplicity of the eigenvalue zero in its spectrum. Cheng and Liu [B. Cheng, B. Liu, On the nullity of graphs, Electron. J. Linear Algebra 16 (2007) 60-67] characterized the extremal graphs attaining the upper bound n-2 and the second upper bound n-3. In this paper, as the continuance of it, we determine the extremal graphs with pendent vertices achieving the third upper bound n-4 and fourth upper bound n-5. We then proceed recursively to construct all graphs with pendent vertices which satisfy η(G)>0. Our results provide a unified approach to determine n-vertex unicyclic (respectively, bicyclic and tricyclic) graphs which achieve the maximal and second maximal nullity and characterize n-vertex extremal trees attaining the second and third maximal nullity. As a consequence we, respectively, determine the nullity sets of trees, unicyclic graphs, bicyclic graphs and tricyclic graphs on n vertices.     

Laplacian coefficients of trees with a given bipartition

Let G be a graph of order n and the Laplacian characteristic polynomial of G. Zhou and Gutman [19] proved that among all trees of order n, the kth coefficient c_k is largest when the tree is a path and is smallest for a star. In this paper, for two given positive integers p and q(p≤q), we characterize the trees with a given bipartition (p,q) which have the minimal and second minimal Laplacian coefficients.     

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.     

The spectra of some trees and bounds for the largest eigenvalue of any tree

Let T be an unweighted tree of k levels such that in each level the vertices have equal degree. Let n_k−j+1 and d_k−j+1 be the number of vertices and the degree of them in the level j. We find the eigenvalues of the adjacency matrix and Laplacian matrix of T for the case of two vertices in level 1 (n_k = 2), including results concerning to their multiplicity. They are the eigenvalues of leading principal submatrices of nonnegative symmetric tridiagonal matrices of order k × k. The codiagonal entries for these matrices are , 2 ? j ? k, while the diagonal entries are 0, …, 0, ±1, in the case of the adjacency matrix, and d₁, d₂, …, d_k−1, d_k ± 1, in the case of the Laplacian matrix. Finally, we use these results to find improved upper bounds for the largest eigenvalue of the adjacency matrix and of the Laplacian matrix of any given tree.     

Sharp bounds for the largest eigenvalue of the signless Laplacian of a graph

Let G be a simple connected graph with n vertices and m edges. Denote the degree of vertex v_i by d(v_i). The matrix Q(G)=D(G)+A(G) is called the signless Laplacian of G, where D(G)=diag(d(v₁),d(v₂),…,d(v_n)) and A(G) denote the diagonal matrix of vertex degrees and the adjacency matrix of G, respectively. Let q₁(G) be the largest eigenvalue of Q(G). In this paper, we first present two sharp upper bounds for q₁(G) involving the maximum degree and the minimum degree of the vertices of G and give a new proving method on another sharp upper bound for q₁(G). Then we present three sharp lower bounds for q₁(G) involving the maximum degree and the minimum degree of the vertices of G. Moreover, we determine all extremal graphs which attain these sharp bounds.     

On the sum of Laplacian eigenvalues of graphs

Let k be a natural number and let G be a graph with at least k vertices. Brouwer conjectured that the sum of the k largest Laplacian eigenvalues of G is at most , where e(G) is the number of edges of G. We prove this conjecture for k=2. We also show that if G is a tree, then the sum of the k largest Laplacian eigenvalues of G is at most e(G)+2k-1.     

Extremal problems on detectable colorings of trees

Let G be a connected graph of order 3 or more and let be a coloring of the edges of G (where adjacent edges may be colored the same). For each vertex v of G, the color code of v is the k-tuple c(v)=(a₁,a₂,…,a_k), where a_i is the number of edges incident with v that are colored i (1?i?k). The coloring c is called detectable if distinct vertices have distinct color codes; while the detection number det(G) of G is the minimum positive integer k for which G has a detectable k-coloring. For each integer n?3, let D_T(n) be the maximum detection number among all trees of order n and d_T(n) the minimum detection number among all trees of order n. The numbers D_T(n) and d_T(n) are determined for all integers n?3. Furthermore, it is shown that for integers k?2 and n?3, there exists a tree T of order n having det(T)=k if and only if d_T(n)?k?D_T(n).     

Cycle extendability in graphs and digraphs

In 1990, Hendry conjectured that all chordal Hamiltonian graphs are cycle extendable, that is, the vertices of each non-Hamiltonian cycle are contained in a cycle of length one greater. Let A be a symmetric (0,1)-matrix with zero main diagonal such that A is the adjacency matrix of a chordal Hamiltonian graph. Hendry’s conjecture in this case is that every k×k principle submatrix of A that dominates a full cycle permutation k×k matrix is a principle submatrix of a (k+1)×(k+1) principle submatrix of A that dominates a (k+1)×(k+1) full cycle permutation matrix. This article generalizes the concept of cycle-extendability to S-extendable; that is, with S⊆{1,2,…,n} and G a graph on n vertices, G is S-extendable if the vertices of every non-Hamiltonian cycle are contained in a cycle length i greater, where i∈S. We investigate this concept in directed graphs and in particular tournaments, i.e., anti-symmetric matrices with zero main diagonal.     

On the signless Laplacian spectral radius of graphs with cut vertices

In this paper, we show that among all the connected graphs with n vertices and k cut vertices, the maximal signless Laplacian spectral radius is attained uniquely at the graph G_n,k, where G_n,k is obtained from the complete graph K_n-k by attaching paths of almost equal lengths to all vertices of K_n-k. We also give a new proof of the analogous result for the spectral radius of the connected graphs with n vertices and k cut vertices (see [A. Berman, X.-D. Zhang, On the spectral radius of graphs with cut vertices, J. Combin. Theory Ser. B 83 (2001) 233-240]). Finally, we discuss the limit point of the maximal signless Laplacian spectral radius.     

On the Laplacian coefficients of graphs under some transformations

We generalize three approaches on graph transformations, respectively, from Stevanovi? and Ili? (2009) [16] and Tan (2011) [19]. We also generalize an approach of graph transformations on the spectral radius of adjacency matrix into the Laplacian coefficients of graphs from Li and Feng (1979) [26]. Moreover, we determine the unique tree having the third maximal Laplacian coefficients among all n-vertex trees.     

Laplacian energy of a graph

Let G be a graph with n vertices and m edges. Let λ₁, λ₂, … , λ_n be the eigenvalues of the adjacency matrix of G, and let μ₁, μ₂, … , μ_n be the eigenvalues of the Laplacian matrix of G. An earlier much studied quantity is the energy of the graph G. We now define and investigate the Laplacian energy as . There is a great deal of analogy between the properties of E(G) and LE(G), but also some significant differences.     

Proof of conjecture involving the second largest signless Laplacian eigenvalue and the index of graphs

Let G = (V, E) be a simple graph. Denote by D(G) the diagonal matrix of its vertex degrees and by A(G) its adjacency matrix. Then the signless Laplacian matrix of G is Q(G) = D(G) + A(G). In [5], Cvetkovi? et al. have given the following conjecture involving the second largest signless Laplacian eigenvalue (q₂) and the index (λ₁) of graph G (see also Aouchiche and Hansen [1]):

     

An explicit formula for eigenvalues of Bethe trees and upper bounds on the largest eigenvalue of any tree

A Bethe tree B_d,k is a rooted unweighted of k levels in which the root vertex has degree equal to d, the vertices at level j(2?j?k-1) have degree equal to (d+1) and the vertices at level k are the pendant vertices. In this paper, we first derive an explicit formula for the eigenvalues of the adjacency matrix of B_d,k. Moreover, we give the corresponding multiplicities. Next, we derive an explicit formula for the simple nonzero eigenvalues, among them the largest eigenvalue, of the Laplacian matrix of B_d,k. Finally, we obtain upper bounds on the largest eigenvalue of the adjacency matrix and of the Laplacian matrix of any tree T. These upper bounds are given in terms of the largest vertex degree and the radius of T, and they are attained if and only if T is a Bethe tree.     

Spectral radius of digraphs with given dichromatic number

Let D be a digraph with vertex set V(D). A partition of V(D) into k acyclic sets is called a k-coloring of D. The minimum integer k for which there exists a k-coloring of D is the dichromatic number χ(D) of the digraph D. Denote G_n,k the set of the digraphs of order n with the dichromatic number k≥2. In this note, we characterize the digraph which has the maximal spectral radius in G_n,k. Our result generalizes the result of [8] by Feng et al.