Search

In this paper, we completely characterize all the trees on n vertices with diameter d for which there is a symmetric matrix with nullity n − d and n − d − 1 , respectively. These characterizations cover all recent results proved for the standard 0 − 1 adjacency matrices. Here a new technique is developed for the general case, breaking the limitation of star complement technique for the standard 0 − 1 adjacency matrices. [ABSTRACT FROM AUTHOR]

Let G be a graph on n vertices. Denote by m G , θ the multiplicity of θ as an eigenvalue of the adjacency matrix of G. In a recent paper, when G is a unicyclic graph, Tian and Wang showed that m G , θ ≤ ⌊ n − 2 3 ⌋ when n ≥ 11 and θ 2 is an integer larger than 1. Motivated by it, we establish an upper bound of m G , θ for any fixed real number θ , generalizing the result of Tian and Wang. Some new techniques are developed to realize the generalization. [ABSTRACT FROM AUTHOR]

The asymptotic distribution theory for the coefficients of polynomials is an important branch in asymptotic analysis. In this paper, we aim to apply the asymptotic distribution theory to spectral graph theory, and establish the conditions under which the coefficients of the characteristic polynomials of adjacency matrices of bipartite graphs and skew-adjacency matrices of oriented graphs are approximately normal distributed. [ABSTRACT FROM AUTHOR]

Let T be a tree on n vertices. Denote by m T , θ the multiplicity of θ as an eigenvalue of the adjacency matrix of T. From two previous publications of Rowlinson and Wong et al., it is shown that m T , 0 ≤ n − 2 , m T , θ ≤ n − 3 2 if θ ≠ 0 , and m T , θ ≤ n − 4 3 if θ ≠ 0 , ± 1 and n ≥ 7. In this note, we exploit the Parter-Wiener Theorem (different from the star complement technique used in previous publications) to obtain an upper bound for m T , θ for any fixed real number θ , thereby generalizing the results of Rowlinson and Wong et al., as well as two new papers from Tian and Wang, and Zhang et al. [ABSTRACT FROM AUTHOR]

The ABC matrix of a graph G , proposed by Estrada in 2017, can be regarded as a weighed version of adjacency matrices of graphs, in which the (u , v) -entry is equal to d u + d v − 2 d u d v if uv is an edge of a graph G , and 0 otherwise, where d u represents the degree of u in G. The research about ABC spectral radius (largest eigenvalue of ABC matrix) of graphs is rather active in recent years. In this paper, we characterize the bicyclic graphs with the first two maximum ABC spectral radii, which are just the unique two bicyclic graphs of order n with maximum degree n − 1 if n ≥ 7. [ABSTRACT FROM AUTHOR]

The distance Laplacian eigenvalues of a connected graph G are the eigenvalues of its distance Laplacian matrix L ( G ) , defined as L ( G ) = T r ( G ) − D ( G ) , where T r ( G ) is the diagonal matrix of vertex transmissions of G , and D ( G ) is the distance matrix of G . In this paper, we determine the unique unicyclic graphs with maximum largest distance Laplacian eigenvalue and minimum second largest distance Laplacian eigenvalue, respectively. [ABSTRACT FROM AUTHOR]

Let m A ( 0 ) denote the nullity of a given matrix A of order n . Set A ( α ) for the principal submatrix of A obtained after deleting the rows and columns indexed by the nonempty subset α of { 1 , … , n } . When m A ( α ) ( 0 ) = m A ( 0 ) + | α | , we call α a P-set of A . In this paper, we classify all of the trees T for which there exists a matrix A whose graph is T and containing a P-set of maximum size. Our characterization does not depend on whether the acyclic matrices are singular or nonsingular. [ABSTRACT FROM AUTHOR]

Abstract: It is known that for any nonsingular acyclic matrix of order n, the maximum number of P-vertices is n if n is even, and if n is odd. In this paper, we thoroughly characterize the trees where those bounds are achieved. In addition, for those trees and for any nonnegative integer k less than or equal to the extremal number of P-vertices, we provide an algorithm to construct a nonsingular matrix whose graph is the given tree and the number of P-vertices is k. Illustrative examples are given. [Copyright &y& Elsevier]

Abstract: We classify all of the trees T, on n vertices, for which there exists a singular matrix A whose graph is T, such that the number of P-vertices is . As a consequence, we will be able to answer in the negative to a question proposed recently by Kim and Shader on the maximal number of P-vertices of a singular acyclic matrix. Several examples are provided. [Copyright &y& Elsevier]

Abstract: For a graph G with eigenvalues , its Estrada index is defined as . We determine the unique graphs with maximum Estrada indices among graphs with given number of cut vertices, connectivity, and edge connectivity, respectively. [Copyright &y& Elsevier]

Abstract: Let G be a graph with n vertices and edges, and let be the Laplacian eigenvalues of G. Let , where . Brouwer conjectured that for . It has been shown in Haemers et al. that the conjecture is true for trees. We give upper bounds for , and in particular, we show that the conjecture is true for unicyclic and bicyclic graphs. [Copyright &y& Elsevier]

Abstract: The Estrada index of a graph G is defined as , where are the eigenvalues of G. We determine the unique unicyclic graph with maximum Estrada index, the unique bipartite unicyclic graph with maximum Estrada index, and the unique bipartite unicyclic graph of a given bipartition with maximum Estrada index. We also show that only two graphs are possible to be the unicyclic graph(s) with minimum Estrada index. [Copyright &y& Elsevier]

Abstract: The Estrada index of a graph G is defined as , where are the eigenvalues of its adjacency matrix. We determine the unique tree with maximum Estrada index among the set of trees with given number of pendant vertices. As applications, we determine trees with maximum Estrada index among the set of trees with given matching number, independence number, and domination number, respectively. Finally, we give a proof of a conjecture in [J. Li, X. Li, L. Wang, The minimal Estrada index of trees with two maximum degree vertices, MATCH Commun. Math. Comput. Chem. 64 (2010) 799–810] on trees with minimum Estrada index among the set of trees with two adjacent vertices of maximum degree. [Copyright &y& Elsevier]

Abstract: The Estrada index of a graph G is defined as , where are the eigenvalues of G. The Laplacian Estrada index of a graph G is defined as , where 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. [Copyright &y& Elsevier]