The number of independent sets in unicyclic graphs with a given diameter

Let U_n,d denote the set of unicyclic graphs with a given diameter d. In this paper, the unique unicyclic graph in U_n,d with the maximum number of independent sets, is characterized.     

An edge-grafting theorem on Laplacian spectra of graphs and its application

Let 𝒰(n,?d) be the class of unicyclic graphs on n vertices with diameter d. This article presents an edge-grafting theorem on Laplacian spectra of graphs. By applying this theorem, we determine the unique graph with the maximum Laplacian spectral radius in 𝒰(n,?d). This extremal graph is different from that for the corresponding problem on the adjacency spectral radius as done by Liu et al. [Q. Liu, M. Lu, and F. Tian, On the spectral radius of unicyclic graphs with fixed diameter, Linear Algebra Appl. 420 (2007), 449–457].     

The smallest values of algebraic connectivity for unicyclic graphs

The algebraic connectivity of G is the second smallest eigenvalue of its Laplacian matrix. Let U_n be the set of all unicyclic graphs of order n. In this paper, we will provide the ordering of unicyclic graphs in U_n up to the last seven graphs according to their algebraic connectivities when n≥13. This extends the results of Liu and Liu [Y. Liu, Y. Liu, The ordering of unicyclic graphs with the smallest algebraic connectivity, Discrete Math. 309 (2009) 4315-4325] and Guo [J.-M. Guo, A conjecture on the algebraic connectivity of connected graphs with fixed girth, Discrete Math. 308 (2008) 5702-5711].     

On the nullity and the matching number of unicyclic graphs

Let G be a graph with n vertices and ν(G) be the matching number of G. Let η(G) denote the nullity of G (the multiplicity of the eigenvalue zero of G). It is well known that if G is a tree, then η(G)=n-2ν(G). Tan and Liu [X. Tan, B. Liu, On the nullity of unicyclic graphs, Linear Alg. Appl. 408 (2005) 212-220] proved that the nullity set of all unicyclic graphs with n vertices is {0,1,…,n-4} and characterized the unicyclic graphs with η(G)=n-4. In this paper, we characterize the unicyclic graphs with η(G)=n-5, and we prove that if G is a unicyclic graph, then η(G) equals , or n-2ν(G)+2. We also give a characterization of these three types of graphs. Furthermore, we determine the unicyclic graphs G with η(G)=0, which answers affirmatively an open problem by Tan and Liu.     

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 .     

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.     

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.     

LARGEST EIGENVALUE OF A UNICYCLIC MIXED GRAPH

The graphs which maximize and minimize respectively the largest eigenvalue over all unicyclic mixed graphs U on n vertices are determined. The unicyclic mixed graphs U with the largest eigenvalue λ1 (U)=n or λ1 (U)∈ (n ,n 1] are characterized.     

On the multiplicity of Laplacian eigenvalues for unicyclic graphs

Let G be a connected graph of order n and U a unicyclic graph with the same order. We firstly give a sharp bound for m_G(μ), the multiplicity of a Laplacian eigenvalue μ of G. As a straightforward result, m_U(1) ? n ? 2. We then provide two graph operations (i.e., grafting and shifting) on graph G for which the value of m_G(1) is nondecreasing. As applications, we get the distribution of m_U (1) for unicyclic graphs on n vertices. Moreover, for the two largest possible values of m_U(1) ∈ {n ? 5, n ? 3}, the corresponding graphs U are completely determined.

     

On the spectral radius of bipartite graphs with given diameter

Let GB(n,d) be the set of bipartite graphs with order n and diameter d. This paper characterizes the extremal graph with the maximal spectral radius in GB(n,d). Furthermore, the maximal spectral radius is a decreasing function on d. At last, bipartite graphs with the second largest spectral radius are determined.     

On the least eigenvalue of a unicyclic mixed graph

Using the result on Fiedler vectors of a simple graph, we obtain a property on the structure of the eigenvectors of a nonsingular unicyclic mixed graph corresponding to its least eigenvalue. With the property, we get some results on minimizing and maximizing the least eigenvalue over all nonsingular unicyclic mixed graphs on n vertices with fixed girth. In particular, the graphs which minimize and maximize, respectively, the least eigenvalue are given over all such graphs with girth 3.     

First eigenvalue and first eigenvectors of a nonsingular unicyclic mixed graph

Let G be a mixed graph and let L(G) be the Laplacian matrix of the graph G. The first eigenvalue and the first eigenvectors of G are respectively referred to the least nonzero eigenvalue and the corresponding eigenvectors of L(G). In this paper we focus on the properties of the first eigenvalue and the first eigenvectors of a nonsingular unicyclic mixed graph (abbreviated to a NUM graph). We introduce the notion of characteristic set associated with the first eigenvectors, and then obtain some results on the sign structure of the first eigenvectors. By these results we determine the unique graph which minimizes the first eigenvalue over all NUM graphs of fixed order and fixed girth, and the unique graph which minimizes the first eigenvalue over all NUM graphs of fixed order.     

On the eccentric distance sum of trees and unicyclic graphs

Let G be a simple connected graph with the vertex set V(G). The eccentric distance sum of G is defined as ξd(G)=_∑v∈V(G)ε(v)DG(v), where ε(v) is the eccentricity of the vertex v and DG(v)=_∑u∈V(G)d(u,v) is the sum of all distances from the vertex v. In this paper we characterize the extremal unicyclic graphs among n-vertex unicyclic graphs with given girth having the minimal and second minimal eccentric distance sum. In addition, we characterize the extremal trees with given diameter and minimal eccentric distance sum.     

On tricyclic graphs of a given diameter with minimal energy

The energy of a graph is defined as the sum of the absolute values of all the eigenvalues of the graph. Let G(n,d) be the class of tricyclic graphs G on n vertices with diameter d and containing no vertex disjoint odd cycles C_p,C_q of lengths p and q with p+q≡2(mod4). In this paper, we characterize the graphs with minimal energy in G(n,d).     

A short and unified proof of Yu et al.?s two results on the eccentric distance sum

The eccentric distance sum (EDS) is a novel topological index that offers a vast potential for structure activity/property relationships. For a connected graph G, the eccentric distance sum is defined as ξd(G)=_∑v∈V(G)ecG(v)DG(v), where ecG(v) is the eccentricity of a vertex v in G and DG(v) is the sum of distances of all vertices in G from v. More recently, Yu et al. [G. Yu, L. Feng, A. Ili?, On the eccentric distance sum of trees and unicyclic graphs, J. Math. Anal. Appl. 375 (2011) 99-107] proved that for an n-vertex tree T, ξd(T)?4n²−9n+5, with equality holding if and only if T is the n-vertex star Sn, and for an n-vertex unicyclic graph G, ξd(G)?4n²−9n+1, with equality holding if and only if G is the graph obtained by adding an edge between two pendent vertices of n-vertex star. In this note, we give a short and unified proof of the above two results.     

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.     

Even graphs

A nontrivial connected graph G is called even if for each vertex v of G there is a unique vertex v such that d(v, v ) = diam G. Special classes of even graphs are defined and compared to each other. In particular, an even graph G is called symmetric if d(u, v) + d(u, v ) = diam G for all u, v ∈ V(G). Several properties of even and symmetric even graphs are stated. For an even graph of order n and diameter d other than an even cycle it is shown that n ≥ 3d – 1 and conjectured that n ≥ 4d – 4. This conjecture is proved for symmetric even graphs and it is shown that for each pair of integers n, d with n even, d ≥ 2 and n ≥ 4d – 4 there exists an even graph of order n and diameter d. Several ways of constructing new even graphs from known ones are presented.     

Bounds on Randi? indices

The general Randi? index of a molecular graph G is the sum of [d(u)d(v)]^α over all edges uv∈G, where d(v) denotes the degree of the vertex v in G and α is an arbitrary number. When α=−1/2, it is called the Randi? index. Delorme et al. stated a best possible lower bound on the Randi? index of a triangle-free graph with given minimum degree. Their false proof was pointed out by Liu et al. In this note, we derive some sharp bounds on the general Randi? index which implies their lower bound for triangle-free graphs of order n with maximum degree at most n/4, and also prove it for triangle-free graphs with small minimum degree.     

Note on unicyclic graphs with given number of pendent vertices and minimal energy

For a simple graph G, the energy E(G) is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix. Let G(n,p) denote the set of unicyclic graphs with n vertices and p pendent vertices. In [H. Hua, M. Wang, Unicyclic graphs with given number of pendent vertices and minimal energy, Linear Algebra Appl. 426 (2007) 478-489], Hua and Wang discussed the graphs that have minimal energy in G(n,p), and determined the minimal-energy graphs among almost all different cases of n and p. In their work, certain case of the values was left as an open problem in which the minimal-energy species have to be chosen in two candidate graphs, but cannot be determined by comparing of the corresponding coefficients of their characteristic polynomials. This paper aims at solving the problem completely, by using the well-known Coulson integral formula.     

On the nullity of tricyclic graphs

The nullity of a graph G, denoted by η(G), is the multiplicity of the eigenvalue zero in its spectrum. It is known that η(G)?n-2 if G is a simple graph on n vertices and G is not isomorphic to nK₁. The extremal graphs attaining the upper bound n-2 and the second upper bound n-3 have been obtained. In this paper, the graphs with nullity n-4 are characterized. Furthermore the tricyclic graphs with maximum nullity are discussed.