Eigenvalues and diameter

Let G be a connected graph of order n. The diameter of a graph is the maximum distance between any two vertices of G. In this paper, we will give some bounds on the diameter of G in terms of eigenvalues of adjacency matrix and Laplacian matrix, respectively.     

Eigenvalues of 2-edge-coverings

A 2-edge-covering between G and H is an onto homomorphism from the vertices of G to the vertices of H so that each edge is covered twice and edges in H can be lifted back to edges in G. In this note we show how to compute the spectrum of G by computing the spectrum of two smaller graphs, namely a (modified) form of the covered graph H and another graph which we term the anti-cover. This is done for both the adjacency matrix and the normalized Laplacian. We also give an example of two anti-cover graphs which have the same normalized Laplacian, and state a generalization for directed graphs.     

On the characteristic polynomial of a special class of graphs and spectra of balanced trees

Let H be a simple graph with n vertices and G be a sequence of n rooted graphs G₁,G₂,…,G_n. Godsil and McKay [C.D. Godsil, B.D. McKay, A new graph product and its spectrum, Bull. Austral. Math. Soc. 18 (1978) 21-28] defined the rooted product H(G), of H by G by identifying the root vertex of G_i with the ith vertex of H, and determined the characteristic polynomial of H(G). In this paper we prove a general result on the determinants of some special matrices and, as a corollary, determine the characteristic polynomials of adjacency and Laplacian matrices of H(G).Rojo and Soto [O. Rojo, R. Soto, The spectra of the adjacency matrix and Laplacian matrix for some balanced trees, Linear Algebra Appl. 403 (2005) 97-117] computed the characteristic polynomials and the spectrum of adjacency and Laplacian matrices of a class of balanced trees. As an application of our results, we obtain their conclusions by a simple method.     

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 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 graphs whose Laplacian matrices have distinct integer eigenvalues

In this paper, we investigate graphs for which the corresponding Laplacian matrix has distinct integer eigenvalues. We define the set S_i,n to be the set of all integers from 0 to n, excluding i. If there exists a graph whose Laplacian matrix has this set as its eigenvalues, we say that this set is Laplacian realizable. We investigate the sets S_i,n that are Laplacian realizable, and the structures of the graphs whose Laplacian matrix has such a set as its eigenvalues. We characterize those i < n such that S_i,n is Laplacian realizable, and show that for certain values of i, the set S_i,n is realized by a unique graph. Finally, we conjecture that S_n,n is not Laplacian realizable for n ≥ 2 and show that the conjecture holds for certain values of n. © 2005 Wiley Periodicals, Inc. J Graph Theory     

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.     

Proof of a tiling conjecture of Komlós

A conjecture of Komlós states that for every graph H, there is a constant K such that if G is any n‐vertex graph of minimum degree at least (1 ? (1/χ_cr(H)))n, where χ_cr(H) denotes the critical chromatic number of H, then G contains an H‐matching that covers all but at most K vertices of G. In this paper we prove that the conjecture holds for all sufficiently large values of n. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 180–205, 2003     

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.     

Cycles through particular subgraphs of claw-free graphs

Let G be a 2-connected claw-free graph on n vertices, and let H be a subgraph of G. We prove that G has a cycle containing all vertices of H whenever α₃(H) ≧ κ(G), where α₃(H) denotes the maximum number of vertices of H that are pairwise at distance at least three in G, and κ(G) denotes the connectivity of G. This result is an analog of a result from the thesis of Fournier, and generalizes the result of Zhang that G is hamiltonian if the degree sum of any κ(G) + 1 pairwise nonadjacent vertices is at least n ? κ(G). © 1995 John Wiley & Sons, Inc.     

Path factors of bipartite graphs

A path on n vertices is denoted by P_n. For any graph H, the number of isolated vertices of H is denoted by i(H). Let G be a graph. A spanning subgraph F of G is called a {P₃, P₄, P₅}-factor of G if every component of F is one of P₃, P₄, and P₅. In this paper, we prove that a bipartite graph G has a {P₃, P₄, P₅}-factor if and only if i(G ? S ? M) ≦ 2|S| + |M| for all S ? V(G) and independent M ? E(G).     

On graphs with the largest Laplacian index

Let G be a connected simple graph on n vertices. The Laplacian index of G, namely, the greatest Laplacian eigenvalue of G, is well known to be bounded above by n. In this paper, we give structural characterizations for graphs G with the largest Laplacian index n. Regular graphs, Hamiltonian graphs and planar graphs with the largest Laplacian index are investigated. We present a necessary and sufficient condition on n and k for the existence of a k-regular graph G of order n with the largest Laplacian index n. We prove that for a graph G of order n ⩾ 3 with the largest Laplacian index n, G is Hamiltonian if G is regular or its maximum vertex degree is Δ(G) = n/2. Moreover, we obtain some useful inequalities concerning the Laplacian index and the algebraic connectivity which produce miscellaneous related results. The first author is supported by NNSF of China (No. 10771080) and SRFDP of China (No. 20070574006). The work was done when Z. Chen was on sabbatical in China.     

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.     

Decompositions of complete graphs and complete bipartite graphs into isomorphic supersubdivision graphs

A graph H is called a supersubdivison of a graph G if H is obtained from G by replacing every edge uv of G by a complete bipartite graph K_2,m (m may vary for each edge) by identifying u and v with the two vertices in K_2,m that form one of the two partite sets. We denote the set of all such supersubdivision graphs by SS(G). Then, we prove the following results.

1. Each non-trivial connected graph G and each supersubdivision graph HSS(G) admits an α-valuation. Consequently, due to the results of Rosa (in: Theory of Graphs, International Symposium, Rome, July 1966, Gordon and Breach, New York, Dunod, Paris, 1967, p. 349) and El-Zanati and Vanden Eynden (J. Combin. Designs 4 (1996) 51), it follows that complete graphs K_2cq+1 and complete bipartite graphs K_mq,nq can be decomposed into edge disjoined copies of HSS(G), for all positive integers m,n and c, where q=|E(H)|.

2. Each connected graph G and each supersubdivision graph in SS(G) is strongly n-elegant, where n=|V(G)| and felicitous.

3. Each supersubdivision graph in EASS(G), the set of all even arbitrary supersubdivision graphs of any graph G, is cordial.

Further, we discuss a related open problem.     

On the eigenvalues of Cayley graphs on the symmetric group generated by a complete multipartite set of transpositions

Given a finite simple graph G with n vertices, we can construct the Cayley graph on the symmetric group S _n generated by the edges of G, interpreted as transpositions. We show that, if G is complete multipartite, the eigenvalues of the Laplacian of Cay (G) have a simple expression in terms of the irreducible characters of transpositions and of the Littlewood–Richardson coefficients. As a consequence, we can prove that the Laplacians of G and of Cay (G) have the same first nontrivial eigenvalue. This is equivalent to saying that Aldous’s conjecture, asserting that the random walk and the interchange process have the same spectral gap, holds for complete multipartite graphs.     

Generalization for Laplacian energy

Let G be a simple graph with n vertices and m edges. Let λ1, λ2,…, λn, be the adjacency spectrum of G, and let μ1, μ2,…, μn be the Laplacian spectrum of G. The energy of G is E（G） = n∑i=1｜λi｜, while the Laplacian energy of G is defined as LE（G） = n∑i=1｜μi-2m/n｜ Let γ1, γ2, ~ …, γn be the eigenvalues of Hermite matrix A. The energy of Hermite matrix as HE（A） = n∑i=1｜γi-tr（A）/n｜ is defined and investigated in this paper. It is a natural generalization of E（G） and LE（G）. Thus all properties about energy in unity can be handled by HE（A）.     

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.     

Doubly stochastic graph matrices,II

If G is a graph on n vertices, its Laplacian matrix L(G) = D(G) - A(G) is the difference of the diagonal matrix of vertex degrees and the adjacency matrix. The main purpose of this note is to continue the study of the positive definite, doubly stochastic graph matrix (I_n + L(G))?¹= ω(G) = (w_ij). If, for example, w(G) = min w_ij, then w(G)≥0 with equality if and only if G is disconnected and w(G) ≤ l/(n + 1) with equality if and only if G = K_n. If i¦j, then w_ii ≥2wij, with equality if and only if the ith vertex has degree n - 1. In a sense made precise in the note, max w,, identifies most remote vertices of G. Relations between these new graph invariants and the algebraic connectivity emerge naturally from the fact that the second largest eigenvalue of ω(G) is 1/(1 + a(G)).     

On graphs with prescribed median I

The distance of a vertex u in a connected graph H is the sum of all the distances from u to the other vertices of H. The median M(H) of H is the subgraph of H induced by the vertices of minimum distance. For any graph G, let f(G) denote the minimum order of a connected graph H satisfying M(H) ? G. It is shown that if G has n vertices and minimum degree δ then f(G) ? 2n ? δ + 1. Graphs having both median and center prescribed are constructed. It is also shown that if the vertices of a K_r are removed from a graph H, then at most r components of the resulting graph contain median vertices of H.