Search

Let B ( n , q ) be the class of block graphs on n vertices having all their blocks of the same size. We prove that if G ∈ B ( n , q ) has at most three pairwise adjacent cut vertices then the minimum spectral radius ρ ( G ) is attained at a unique graph. In addition, we present a lower bound for ρ ( G ) when G ∈ B ( n , q ) .

A matrix-weighted graph is an undirected graph with a $k\times k$ positive semidefinite matrix assigned to each edge. There are natural generalizations of the Laplacian and adjacency matrices for such graphs. These matrices can be used to define and control expansion for matrix-weighted graphs. In particular, an analogue of the expander mixing lemma and one half of a Cheeger-type inequality hold for matrix-weighted graphs. A new definition of a matrix-weighted expander graph suggests the tantalizing possibility of families of matrix-weighted graphs with better-than-Ramanujan expansion., 21 pages, 2 figures

We give lower bounds on the size and total size of clique partitions of a graph in terms of its spectral radius and minimum degree, and derive a spectral upper bound for the maximum number of edge-disjoint t-cliques. The extremal graphs attaining the bounds are exactly the block graphs of Steiner 2-designs and the regular graphs with K t -decompositions, respectively.

Hoffman's ratio bound is an upper bound for the independence number of a regular graph in terms of the eigenvalues of the adjacency matrix. The bound has proved to be very useful and has been applied many times. Hoffman did not publish his result, and for a great number of users the emergence of Hoffman's bound is a black hole. With his note I hope to clarify the history of this bound and some of its generalizations.

In this paper, structural properties of chordal graphs are analysed, in order to establish a relationship between these structures and integer Laplacian eigenvalues. We present the characterization of chordal graphs with equal vertex and algebraic connectivities, by means of the vertices that compose the minimal vertex separators of the graph; we stablish a sufficient condition for the cardinality of a maximal clique to appear as an integer Laplacian eigenvalue. Finally, we review two subclasses of chordal graphs, showing for them some new properties., 15 pages, 5 figures

For a given graph $\mathcal{G}$ of order $n$ with $m$ edges, and a real symmetric matrix associated to the graph, $M\left(\mathcal{G}\right)\in\mathbb{R}^{n\times n}$, the interlacing graph reduction problem is to find a graph $\mathcal{G}_{r}$ of order $r

In quantum information theory there is a construction for quantum channels, appropriately called a quantum graph, that generalizes the confusability graph construction for classical channels in classical information theory. In this paper, we provide a definition of connectedness for quantum graphs that generalizes the classical definition. This is used to prove a quantum version of a particular case of the classical tree-packing theorem from graph theory. Generalizations for the related notions of $k$-connectedness and of orthogonal representation are also proposed for quantum graphs, and it is shown that orthogonal representations have the same implications for connectedness as they do in the classical case., Comment: 15 pages

Dual Seidel switching is a graph operation introduced by W. Haemers in 1984. This operation can change the graph, however it does not change its bipartite double, and because of this, the operation leaves the squares of the eigenvalues invariant. Thus, if a graph is integral then it is still integral after dual Seidel switching. In this paper two new infinite families of integral graphs are obtained by applying dual Seidel switching to the Star graphs and the Odd graphs. In particular, three new 4-regular integral graphs with their spectra are found.

Quantum walks on undirected graphs have been studied using symmetric matrices, such as the adjacency or Laplacian matrix, and many results about perfect state transfer are known. We extend some of those results to oriented graphs. We also study the phenomena, unique to oriented graphs, of multiple state transfer, where there is a set of vertices such that perfect state transfer occurs between every pair in that set. We give a characterization of multiple state transfer, and a new example of a graph where it occurs., Comment: 17 pages, 3 figures

For a graph $G=(V, E)$ and $i, j\in V$, denote the distance between $i$ and $j$ in $G$ by $D(i, j)$ and the degrees of $i$, $j$ by $d_i$, $d_j$, respectively. Let $f(D(i, j), d_{i}, d_{j})$ be a function symmetric in $i$ and $j$. Define a matrix $W_f(G)$, called the weighted distance matrix, of $G$, with the $ij$-entry $W_f(G)(i, j)=f(D(i, j), d_{i}, d_{j})$ if $i\neq j$ and $W_f(G)(i, j)=0$ if $i=j$. In this paper, we prove that if the symmetric function $f$ satisfies that $f(D(i, j), (1+o(1))np, (1+o(1))np)=(1+o(1))f(D(i, j), np, np)$, then for almost all graphs $G_p$ in the $Erd\ddot{o}s$-$R\acute{e}nyi$ random graph model $\mathcal{G}_{n, p}$, the energy of $W_f(G_p)$ is $\{(\frac{8}{3\pi}\sqrt{p(1-p)}+o(1))\cdot|f(1, np, np)-f(2, np, np)|+o(|f(2, np, np)|)\}\cdot n^{3/2}$. As a consequence, we give the asymptotic values of energies of a variety of weighted distance matrices with function $f$ from distance-based only and mixed with degree-distance-based topological indices of chemical use. This generalizes our former result with only degree-based weights., Comment: 15 pages

Distance ideals generalize the Smith normal form of the distance matrix of a graph. The family of graphs with 2 trivial distance ideals contains the family of graphs whose distance matrix has at most 2 invariant factors equal to 1. Here we give an infinite family of forbidden induced subgraphs for the graphs with 2 trivial distance ideals. These are also related with other well known graph classes., Some typos were corrected

Recently, Anderson et al. (2019) proposed the concept of rankability, which refers to a dataset's inherent ability to produce a meaningful ranking of its items. In the same paper, they proposed a rankability measure that is based on an integer program for computing the minimum number of edge changes made to a directed graph in order to obtain a complete dominance graph, i.e., an acyclic tournament graph. In this article, we prove a spectral-degree characterization of complete dominance graphs and apply this characterization to produce a new measure of rankability that is cost-effective and more widely applicable. We support the details of our algorithm with several results regarding the conditioning of the Laplacian spectrum of complete dominance graphs and the Hausdorff distance between their Laplacian spectrum and that of an arbitrary directed graph with weights between zero and one. Finally, we analyze the rankability of datasets from the world of chess and college football.

The purpose of this paper is to highlight the role played by the anti-regular graph within the class of threshold graphs. Using the fact that every threshold graph contains a maximal anti-regular graph, we show that some known results, and new ones, on the spectral properties of threshold graphs can be deduced from (i) the known results on the eigenvalues of anti-regular graphs, (ii) the subgraph structure of threshold graphs, and (iii) eigenvalue interlacing. In particular, we prove a strengthened version of the recently proved fact that no threshold graph contains an eigenvalue in the interval Ω = [ − 1 − 2 2 , − 1 + 2 2 ] , except possibly the trivial eigenvalues −1 and/or 0, determine the inertia of a threshold graph, and give partial results on a conjecture regarding the optimality of the non-trivial eigenvalues of an anti-regular graph within the class of threshold graphs.

We discuss the Grassmann graph $J_q(N,D)$ with $N \geq 2D$, having as vertices the $D$-dimensional subspaces of an $N$-dimensional vector space over the finite field $\mathbb{F}_q$. This graph is distance-regular with diameter $D$; to avoid trivialities we assume $D\geq 3$. Fix a pair of a Delsarte clique $C$ of $J_q(N,D)$ and a vertex $x$ in $C$. We construct a $2D$-dimensional irreducible module $\mathbf{W}$ for the Terwilliger algebra $\mathbf{T}$ of $J_q(N,D)$ associated with the pair $x$, $C$. We show that $\mathbf{W}$ is an irreducible module for the confluent Cherednik algebra $\mathcal{H}_\mathrm{V}$ and describe how the $\mathbf{T}$-action on $\mathbf{W}$ is related to the $\mathcal{H}_\mathrm{V}$-action on $\mathbf{W}$. Using the $\mathcal{H}_\mathrm{V}$-module $\mathbf{W}$, we define non-symmetric dual $q$-Hahn polynomials and prove their recurrence and orthogonality relations from a combinatorial viewpoint., Comment: 31 pages, 3 figures

A signed graph $\Gamma(G)$ is a graph with a sign attached to each of its edges, where $G$ is the underlying graph of $\Gamma(G)$. The energy of a signed graph $\Gamma(G)$ is the sum of the absolute values of the eigenvalues of the adjacency matrix $A(\Gamma(G))$ of $\Gamma(G)$. The random signed graph model $\mathcal{G}_n(p, q)$ is defined as follows: Let $p, q \ge 0$ be fixed, $0 \le p+q \le 1$. Given a set of $n$ vertices, between each pair of distinct vertices there is either a positive edge with probability $p$ or a negative edge with probability $q$, or else there is no edge with probability $1-(p+ q)$. The edges between different pairs of vertices are chosen independently. In this paper, we obtain an exact estimate of energy for almost all signed graphs. Furthermore, we establish lower and upper bounds to the energy of random multipartite signed graphs., Comment: 11 page, 0 figures. arXiv admin note: text overlap with arXiv:0909.4923 by other authors

In this note we prove that the vertex energy of a graph, as defined in Arizmendi and Juarez (2018), can be calculated in terms of a Coulson integral formula. We present examples of how this formula can be used, and we show some applications to bipartite graphs., 14 pages, 5 figures

It is known that complete multipartite graphs are determined by their distance spectrum but not by their adjacency spectrum. The Seidel spectrum of a graph $G$ on more than one vertex does not determine the graph, since any graph obtained from $G$ by Seidel switching has the same Seidel spectrum. We consider $G$ to be determined by its Seidel spectrum, up to switching, if any graph with the same spectrum is switching equivalent to a graph isomorphic to $G$. It is shown that any graph which has the same spectrum as a complete $k$-partite graph is switching equivalent to a complete $k$-partite graph, and if the different partition sets sizes are $p_1,\ldots, p_l$, and there are at least three partition sets of each size $p_i$, $i=1,\ldots, l$, then $G$ is determined, up to switching, by its Seidel spectrum. Sufficient conditions for a complete tripartite graph to be determined by its Seidel spectrum are discussed, and a conjecture is made on complete tripartite graphs on more than 18 vertices., 12 page 2 figures

Finding a diagonal matrix congruent to $A - cI$ for constants $c$, where $A$ is the adjacency matrix of a graph $G$ allows us to quickly tell the number of eigenvalues in a given interval. If $G$ has clique-width $k$ and a corresponding $k$-expression is known, then diagonalization can be done in time $O(\text{poly}(k) n)$ where $n$ is the order of $G$., Comment: 25 pages

We study the eigenvalues of the unique connected anti-regular graph $A_n$. Using Chebyshev polynomials of the second kind, we obtain a trigonometric equation whose roots are the eigenvalues and perform elementary analysis to obtain an almost complete characterization of the eigenvalues. In particular, we show that the interval $\Omega=[\tfrac{-1-\sqrt{2}}{2}, \tfrac{-1+\sqrt{2}}{2}]$ contains only the trivial eigenvalues $\lambda = -1$ or $\lambda=0$, and any closed interval strictly larger than $\Omega$ will contain eigenvalues of $A_n$ for all $n$ sufficiently large. We also obtain bounds for the maximum and minimum eigenvalues, and for all other eigenvalues we obtain interval bounds that improve as $n$ increases. Moreover, our approach reveals a more complete picture of the bipartite character of the eigenvalues of $A_n$, namely, as $n$ increases the eigenvalues are (approximately) symmetric about the number $-\tfrac{1}{2}$. We also obtain an asymptotic distribution of the eigenvalues as $n\rightarrow\infty$. Finally, the relationship between the eigenvalues of $A_n$ and the eigenvalues of a general threshold graph is discussed., Comment: 20 pages, 6 figures, 1 table

An oriented hypergraph is an oriented incidence structure that generalizes and unifies graph and hypergraph theoretic results by examining its locally signed graphic substructure. In this paper we obtain a combinatorial characterization of the coefficients of the characteristic polynomials of oriented hypergraphic Laplacian and adjacency matrices via a signed hypergraphic generalization of basic figures of graphs. Additionally, we provide bounds on the determinant and permanent of the Laplacian matrix, characterize the oriented hypergraphs in which the upper bound is sharp, and demonstrate that the lower bound is never achieved.

For a graph G, let λ 2 ( G ) denote its second smallest Laplacian eigenvalue. It was conjectured that λ 2 ( G ) + λ 2 ( G ‾ ) ≥ 1 , where G ‾ is the complement of G. In this paper, it is shown that max ⁡ { λ 2 ( G ) , λ 2 ( G ‾ ) } ≥ 2 5 .

In this paper we compute the critical group of the Kneser graph $KG(n,2)$. This is equivalent to computing the Smith normal form of a Laplacian matrix of this graph., The statement of Lemma 2.2, part (4) was missing a case. This has been corrected, and it has no effect on the rest of the paper

Arithmetical structures on a graph were introduced by Lorenzini as some intersection matrices that arise in the study of degenerating curves in algebraic geometry. In this article we study these arithmetical structures, in particular we are interested in the arithmetical structures on complete graphs, paths, and cycles. We begin by looking at the arithmetical structures on a multidigraph from the general perspective of $M$-matrices. As an application, we recover the result of Lorenzini about the finiteness of the number of arithmetical structures on a graph. We give a description on the arithmetical structures on the graph obtained by merging and splitting a vertex of a graph in terms of its arithmetical structures. On the other hand, we give a description of the arithmetical structures on the clique--star transform of a graph, which generalizes the subdivision of a graph. As an application of this result we obtain an explicit description of all the arithmetical structures on the paths and cycles and we show that the number of the arithmetical structures on a path is a Catalan number., 23 pages, 5 Figures, Minor changes

A rose graph is a graph consisting of cycles that all meet in one vertex. We show that except for two specific examples, these rose graphs are determined by the Laplacian spectrum, thus proving a conjecture posed by Lui and Huang [F.J. Liu and Q.X. Huang, Laplacian spectral characterization of 3-rose graphs, Linear Algebra Appl. 439 (2013), 2914--2920]. We also show that if two rose graphs have a so-called universal Laplacian matrix with the same spectrum, then they must be isomorphic. In memory of Horst Sachs (1927-2016), we show the specific case of the latter result for the adjacency matrix by using Sachs' theorem and a new result on the number of matchings in the disjoint union of paths.

The distance matrix of a connected graph is the symmetric matrix with columns and rows indexed by the vertices and entries that are the pairwise distances between the corresponding vertices. We give a construction for graphs which differ in their edge counts yet are cospectral with respect to the distance matrix. Further, we identify a subgraph switching behavior which constructs additional distance cospectral graphs. The proofs for both constructions rely on a perturbation of (most of) the distance eigenvectors of one graph to yield the distance eigenvectors of the other., Comment: 17 pages, 4 figures

Let G be a graph and let A ( G ) be adjacency matrix of G. The positive inertia index (respectively, the negative inertia index) of G, denoted by p ( G ) (respectively, n ( G ) ), is defined to be the number of positive eigenvalues (respectively, negative eigenvalues) of A ( G ) . In this paper, we present the bounds for p ( G ) and n ( G ) as follows: m ( G ) − c ( G ) ≤ p ( G ) ≤ m ( G ) + c ( G ) , m ( G ) − c ( G ) ≤ n ( G ) ≤ m ( G ) + c ( G ) , where m ( G ) and c ( G ) are respectively the matching number and the cyclomatic number of G. Furthermore, we characterize the graphs which attain the upper bounds and the lower bounds respectively.

It is well known that a graph is bipartite if and only if the spectrum of its adjacency matrix is symmetric. In the present paper, this assertion is dissected into three separate matrix results of wider scope, which are extended also to hypermatrices. To this end the concept of bipartiteness is generalized by a new monotone property of cubical hypermatrices, called odd-colorable matrices. It is shown that a nonnegative symmetric $r$-matrix $A$ has a symmetric spectrum if and only if $r$ is even and $A$ is odd-colorable. This result also solves a problem of Pearson and Zhang about hypergraphs with symmetric spectrum and disproves a conjecture of Zhou, Sun, Wang, and Bu. Separately, similar results are obtained for the $H$-spectram of hypermatrices., 17 pages. Corrected proof on p. 13

The distance matrix of a graph $G$ is the matrix containing the pairwise distances between vertices. The distance eigenvalues of $G$ are the eigenvalues of its distance matrix and they form the distance spectrum of $G$. We determine the distance spectra of halved cubes, double odd graphs, and Doob graphs, completing the determination of distance spectra of distance regular graphs having exactly one positive distance eigenvalue. We characterize strongly regular graphs having more positive than negative distance eigenvalues. We give examples of graphs with few distinct distance eigenvalues but lacking regularity properties. We also determine the determinant and inertia of the distance matrices of lollipop and barbell graphs., 20 pages, 3 figures v2. updated acknowledgements

We establish that every embedding of a Grassmann graph in a polar Grassmann graph can be reduced to an embedding in a Grassmann graph or to an embedding in the collinearity graph of a polar space. Also, we consider 3-embeddings, i.e. embeddings preserving all distances not greater than 3, of dual polar graphs whose diameter is not less than 3 in polar Grassmann graphs formed by non-maximal singular subspaces. Using the same arguments we show that every such an embedding can be reduced to an embedding in a Grassmann graph.

Let $G$ be a graph with maximum degree $\Delta$, and let $G^{\sigma}$ be an oriented graph of $G$ with skew adjacency matrix $S(G^{\sigma})$. The skew spectral radius $\rho_s(G^{\sigma})$ of $G^\sigma$ is defined as the spectral radius of $S(G^\sigma)$. The skew spectral radius has been studied, but only few results about its lower bound are known. This paper determines some lower bounds of the skew spectral radius, and then studies the oriented graphs whose skew spectral radii attain the lower bound $\sqrt{\Delta}$. Moreover, we apply the skew spectral radius to the skew energy of oriented graphs, which is defined as the sum of the norms of all the eigenvalues of $S(G^\sigma)$, and denoted by $\mathcal{E}_s(G^\sigma)$. As results, we obtain some lower bounds of the skew energy, which improve the known lower bound obtained by Adiga et al., Comment: 16 pages, 2 figures

We apply interlacing techniques for obtaining lower and upper bounds for the sums of Laplacian eigenvalues of graphs. Mainly, we generalize two theorems of Grone and Grone & Merris, providing tight bounds and studying the cases of equality. As a consequence, some results on well-known parameters of a graph, such as the maximum and minimum cuts, the edge-connectivity, the (almost) dominating number, and the edge isoperimetric number, are derived.

Let $\lambda_1,\dots,\lambda_n$ be the eigenvalues of a graph $G$. For any $k\geq 0$, the $k$-th spectral moment of $G$ is defined by $\M_k(G)=\lambda_1^k+\dots+\lambda_n^k$. We use the fact that $\M_k(G)$ is also the number of closed walks of length $k$ in $G$ to show that among trees $T$ whose degree sequence is $D$ or majorized by $D$, $\M_k(T)$ is maximized by the greedy tree with degree sequence $D$ (constructed by assigning the highest degree in $D$ to the root, the second-, third-, \dots highest degrees to the neighbors of the root, and so on) for any $k\geq 0$. Several corollaries follow, in particular a conjecture of Ili\'c and Stevanovi\'c on trees with given maximum degree, which in turn implies a conjecture of Gutman, Furtula, Markovi\'c and Gli\v{s}i\'c on the Estrada index of such trees, which is defined as $\EE(G)=e^{\lambda_1}+\dots+e^{\lambda_n}$., Comment: 24 pages 5 figures

In this paper, we introduce the class of cored hypergraphs and power hypergraphs, and investigate the properties of their Laplacian H-eigenvalues. From an ordinary graph, one may generate a $k$-uniform hypergraph, called the $k$th power hypergraph of that graph. Power hypergraphs are cored hypergraphs, but not vice versa. Hyperstars, hypercycles, hyperpaths are special cases of power hypergraphs, while sunflowers are a subclass of cored hypergraphs, but not power graphs in general. We show that the largest Laplacian H-eigenvalue of an even-uniform cored hypergraph is equal to its largest signless Laplacian H-eigenvalue. Especially, we find out these largest H-eigenvalues for even-uniform sunflowers. Moreover, we show that the largest Laplacian H-eigenvalue of an odd-uniform sunflower, hypercycle and hyperpath is equal to the maximum degree, i.e., 2. We also compute out the H-spectra of the class of hyperstars. When $k$ is odd, the H-spectra of the hypercycle of size 3 and the hyperpath of length 3 are characterized as well., 27 pages, 3 figures. arXiv admin note: text overlap with arXiv:1304.1315

Let $G$ be a graph of order $n,$ and let $q_{1}(G) \geq ...\geq q_{n}(G) $ be the eigenvalues of the $Q$-matrix of $G$, also known as the signless Laplacian of $G.$ In this paper we give a necessary and sufficient condition for the equality $q_{k}(G) =n-2,$ where $1, Comment: This version fills a gap in one proof, noticed by Rundan Xing

For the class of stably dissipative Lotka–Volterra systems we prove that the rank of its defining matrix, which is the dimension of the associated invariant foliation, is completely determined by the system’s graph.

Let V and V ′ be vector spaces of dimension n and n ′ , respectively. Let k ∈ { 2 , … , n - 2 } and k ′ ∈ { 2 , … , n ′ - 2 } . We describe all isometric and l -rigid isometric embeddings of the Grassmann graph Γ k ( V ) in the Grassmann graph Γ k ′ ( V ′ ) .

In 1970s, Gutman introduced the concept of the energy $\En(G)$ for a simple graph $G$, which is defined as the sum of the absolute values of the eigenvalues of $G$. This graph invariant has attracted much attention, and many lower and upper bounds have been established for some classes of graphs among which bipartite graphs are of particular interest. But there are only a few graphs attaining the equalities of those bounds. We however obtain an exact estimate of the energy for almost all graphs by Wigner's semi-circle law, which generalizes a result of Nikiforov. We further investigate the energy of random multipartite graphs by considering a generalization of Wigner matrix, and obtain some estimates of the energy for random multipartite graphs., 16 pages

The energy of a graph G, denoted by E(G), is defined as the sum of the absolute values of all eigenvalues of G. It is proved that E(G)>= 2(n-��(\bar{G}))>= 2(ch(G)-1) for every graph G of order n, and that E(G)>= 2ch(G) for all graphs G except for those in a few specified families, where \bar{G}, ��(G), and ch(G) are the complement, the chromatic number, and the choice number of G, respectively., to appear in Linear Algebra and its Applications

Let G be a graph with n vertices and m edges and let μ(G) = μ1(G) ⩾ ⋯ ⩾ μn(G) be the eigenvalues of its adjacency matrix. Set s ( G ) = ∑ u ∈ V ( G ) ∣ d ( u ) - 2 m / n ∣ . We prove that s 2 ( G ) 2 n 2 2 m ⩽ μ ( G ) - 2 m n ⩽ s ( G ) . In addition we derive similar inequalities for bipartite G. We also prove that the inequality μ k ( G ) + μ n - k + 2 ( G ¯ ) ⩾ - 1 - 2 2 s ( G ) holds for every k = 2, … , n. Finally we prove that for every graph G of order n, μ n ( G ) + μ n ( G ¯ ) ⩽ - 1 - s 2 ( G ) 2 n 3 . We show that these inequalities are tight up to a constant factor.

For a distance-regular graph with second largest eigenvalue (resp. smallest eigenvalue) \mu1 (resp. \muD) we show that (\mu1+1)(\muD+1), 15 pages, this is submitted to Linear Algebra and Applications.

Suppose $C$ is a subset of non-zero vectors from the vector space $\mathbb{Z}_2^d$. The cubelike graph $X(C)$ has $\mathbb{Z}_2^d$ as its vertex set, and two elements of $\mathbb{Z}_2^d$ are adjacent if their difference is in $C$. If $M$ is the $d\times |C|$ matrix with the elements of $C$ as its columns, we call the row space of $M$ the code of $X$. We use this code to study perfect state transfer on cubelike graphs. Bernasconi et al have shown that perfect state transfer occurs on $X(C)$ at time $\pi/2$ if and only if the sum of the elements of $C$ is not zero. Here we consider what happens when this sum is zero. We prove that if perfect state transfer occurs on a cubelike graph, then it must take place at time $\tau=\pi/2D$, where $D$ is the greatest common divisor of the weights of the code words. We show that perfect state transfer occurs at time $\pi/4$ if and only if D=2 and the code is self-orthogonal., Comment: 10 pages, minor revisions

We investigate the expected value of various graph parameters associated with the minimum rank of a graph, including minimum rank/maximum nullity and related Colin de Verdi\`ere-type parameters. Let $G(v,p)$ denote the usual Erd\H{o}s-R\'enyi random graph on $v$ vertices with edge probability $p$. We obtain bounds for the expected value of the random variables ${\rm mr}(G(v,p))$, ${\rm M}(G(v,p))$, $\nu(G(v,p))$ and $\xi(G(v,p))$, which yield bounds on the average values of these parameters over all labeled graphs of order $v$., Comment: 17 pages, 2 figures

For a simple graph $G$, the energy $E(G)$ is defined as the sum of the absolute values of all eigenvalues of its adjacent matrix. For $\Delta\geq 3$ and $t\geq 3$, denote by $T_a(\Delta,t)$ (or simply $T_a$) the tree formed from a path $P_t$ on $t$ vertices by attaching $\Delta-1$ $P_2$'s on each end of the path $P_t$, and $T_b(\Delta, t)$ (or simply $T_b$) the tree formed from $P_{t+2}$ by attaching $\Delta-1$ $P_2$'s on an end of the $P_{t+2}$ and $\Delta -2$ $P_2$'s on the vertex next to the end. In [X. Li, X. Yao, J. Zhang and I. Gutman, Maximum energy trees with two maximum degree vertices, J. Math. Chem. 45(2009), 962--973], Li et al. proved that among trees of order $n$ with two vertices of maximum degree $\Delta$, the maximal energy tree is either the graph $T_a$ or the graph $T_b$, where $t=n+4-4\Delta\geq 3$. However, they could not determine which one of $T_a$ and $T_b$ is the maximal energy tree. This is because the quasi-order method is invalid for comparing their energies. In this paper, we use a new method to determine the maximal energy tree. It turns out that things are more complicated. We prove that the maximal energy tree is $T_b$ for $\Delta\geq 7$ and any $t\geq 3$, while the maximal energy tree is $T_a$ for $\Delta=3$ and any $t\geq 3$. Moreover, for $\Delta=4$, the maximal energy tree is $T_a$ for all $t\geq 3$ but $t=4$, for which $T_b$ is the maximal energy tree. For $\Delta=5$, the maximal energy tree is $T_b$ for all $t\geq 3$ but $t$ is odd and $3\leq t\leq 89$, for which $T_a$ is the maximal energy tree. For $\Delta=6$, the maximal energy tree is $T_b$ for all $t\geq 3$ but $t=3,5,7$, for which $T_a$ is the maximal energy tree. One can see that for most $\Delta$, $T_b$ is the maximal energy tree, $\Delta=5$ is a turning point, and $\Delta=3$ and 4 are exceptional cases., Comment: 16 pages