Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the $A_{alpha}$-spectra of trees
87
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $G$ be a graph with adjacency matrix $A(G)$ and let $D(G)$ be the diagonal matrix of the degrees of $G$. For every real $alphainleft[ 0,1right],$ define the matrix $A_{alpha}left(Gright) $ as [ A_{alpha}left(Gright) =alpha Dleft(Gright) +(1-alpha)Aleft(Gright) ] where $0leqalphaleq1$. This paper gives several results about the $A_{alpha}$-matrices of trees. In particular, it is shown that if $T_{Delta}$ is a tree of maximal degree $Delta,$ then the spectral radius of $A_{alpha}(T_{Delta})$ satisfies the tight inequality [ rho(A_{alpha}(T_{Delta}))<alphaDelta+2(1-alpha)sqrt{Delta-1}. ] This bound extends previous bounds of Godsil, Lovasz, and Stevanovic. The proof is based on some new results about the $A_{alpha}$-matrices of Bethe trees and generalized Bethe trees. In addition, several bounds on the spectral radius of $A_{alpha}$ of general graphs are proved, implying tight bounds for paths and Bethe trees.
rate research
Read More
Let $G$ be a graph with $n$ vertices, and let $A(G)$ and $D(G)$ denote respectively the adjacency matrix and the degree matrix of $G$. Define $$ A_{alpha}(G)=alpha D(G)+(1-alpha)A(G) $$ for any real $alphain [0,1]$. The $A_{alpha}$-characteristic polynomial of $G$ is defined to be $$ det(xI_n-A_{alpha}(G))=sum_jc_{alpha j}(G)x^{n-j}, $$ where $det(*)$ denotes the determinant of $*$, and $I_n$ is the identity matrix of size $n$. The $A_{alpha}$-spectrum of $G$ consists of all roots of the $A_{alpha}$-characteristic polynomial of $G$. A graph $G$ is said to be determined by its $A_{alpha}$-spectrum if all graphs having the same $A_{alpha}$-spectrum as $G$ are isomorphic to $G$. In this paper, we first formulate the first four coefficients $c_{alpha 0}(G)$, $c_{alpha 1}(G)$, $c_{alpha 2}(G)$ and $c_{alpha 3}(G)$ of the $A_{alpha}$-characteristic polynomial of $G$. And then, we observe that $A_{alpha}$-spectra are much efficient for us to distinguish graphs, by enumerating the $A_{alpha}$-characteristic polynomials for all graphs on at most 10 vertices. To verify this observation, we characterize some graphs determined by their $A_{alpha}$-spectra.
In this paper, we use a new and correct method to determine the $n$-vertex $k$-trees with the first three largest signless Laplacian indices.
Let $T_{n}$ be the set of rooted labeled trees on $set{0,...,n}$. A maximal decreasing subtree of a rooted labeled tree is defined by the maximal subtree from the root with all edges being decreasing. In this paper, we study a new refinement $T_{n,k}$ of $T_n$, which is the set of rooted labeled trees whose maximal decreasing subtree has $k+1$ vertices.
A subtree of a tree is any induced subgraph that is again a tree (i.e., connected). The mean subtree order of a tree is the average number of vertices of its subtrees. This invariant was first analyzed in the 1980s by Jamison. An intriguing open question raised by Jamison asks whether the maximum of the mean subtree order, given the order of the tree, is always attained by some caterpillar. While we do not completely resolve this conjecture, we find some evidence in its favor by proving different features of trees that attain the maximum. For example, we show that the diameter of a tree of order $n$ with maximum mean subtree order must be very close to $n$. Moreover, we show that the maximum mean subtree order is equal to $n - 2log_2 n + O(1)$. For the local mean subtree order, which is the average order of all subtrees containing a fixed vertex, we can be even more precise: we show that its maximum is always attained by a broom and that it is equal to $n - log_2 n + O(1)$.
We prove that for any tree with a vertex of degree at least six, its chromatic symmetric function is not $e$-positive, that is, it cannot be written as a nonnegative linear combination of elementary symmetric functions. This makes significant progress towards a recent conjecture of Dahlberg, She, and van Willigenburg, who conjectured the result for all trees with a vertex of degree at least four. We also provide a series of conditions that can identify when the chromatic symmetric function of a spider, a tree consisting of multiple paths identified at an end, is not $e$-positive. These conditions also generalize to trees and graphs with cut vertices. Finally, by applying a result of Orellana and Scott, we provide a method to inductively calculate certain coefficients in the elementary symmetric function expansion of the chromatic symmetric function of a spider, leading to further $e$-positivity conditions for spiders.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
