Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the maximum mean subtree order of trees
187
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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)$.
rate research
Read More
In this paper we investigate an extremal problem on binary phylogenetic trees. Given two such trees $T_1$ and $T_2$, both with leaf-set ${1,2,...,n}$, we are interested in the size of the largest subset $S subseteq {1,2,...,n}$ of leaves in a common subtree of $T_1$ and $T_2$. We show that any two binary phylogenetic trees have a common subtree on $Omega(sqrt{log{n}})$ leaves, thus improving on the previously known bound of $Omega(loglog n)$ due to M. Steel and L. Szekely. To achieve this improved bound, we first consider two special cases of the problem: when one of the trees is balanced or a caterpillar, we show that the largest common subtree has $Omega(log n)$ leaves. We then handle the general case by proving and applying a Ramsey-type result: that every binary tree contains either a large balanced subtree or a large caterpillar. We also show that there are constants $c, alpha > 0$ such that, when both trees are balanced, they have a common subtree on $c n^alpha$ leaves. We conjecture that it is possible to take $alpha = 1/2$ in the unrooted case, and both $c = 1$ and $alpha = 1/2$ in the rooted case.
Among many topological indices of trees the sum of distances $sigma(T)$ and the number of subtrees $F(T)$ have been a long standing pair of graph invariants that are well known for their negative correlation. That is, among various given classes of trees, the extremal structures maximizing one usually minimize the other, and vice versa. By introducing the local
A subset of vertices is a {it maximum independent set} if no two of the vertices are adjacent and the subset has maximum cardinality. A subset of vertices is called a {it maximum dissociation set} if it induces a subgraph with vertex degree at most 1, and the subset has maximum cardinality. Zito [J. Graph Theory {bf 15} (1991) 207--221] proved that the maximum number of maximum independent sets of a tree of order $n$ is $2^{frac{n-3}{2}}$ if $n$ is odd, and $2^{frac{n-2}{2}}+1$ if $n$ is even and also characterized all extremal trees with the most maximum independent sets, which solved a question posed by Wilf. Inspired by the results of Zito, in this paper, by establishing four structure theorems and a result of $k$-K{o}nig-Egerv{a}ry graph, we show that the maximum number of maximum dissociation sets in a tree of order $n$ is begin{center} $left{ begin{array}{ll} 3^{frac{n}{3}-1}+frac{n}{3}+1, & hbox{if $nequiv0pmod{3}$;} 3^{frac{n-1}{3}-1}+1, & hbox{if $nequiv1pmod{3}$;} 3^{frac{n-2}{3}-1}, & hbox{if $nequiv2pmod{3}$,} end{array} right.$ end{center} and also give complete structural descriptions of all extremal trees on which these maxima are achieved.
We define a class of properties on random plane trees, which we call subtree additive properties, inspired by the combinatorics of certain biologically-interesting properties in a plane tree model of RNA secondary structure. The class of subtree additive properties includes the Wiener index and path length (total ladder distance and total ladder contact distance, respectively, in the biological context). We then investigate the asymptotic distribution of these subtree additive properties on a random plane tree distributed according to a Gibbs distribution arising from the Nearest Neighbor Thermodynamic Model for RNA secondary structure. We show that for any property in the class considered, there is a constant that translates the uniformly weighted random variable to the Gibbs distribution weighted random variable (and we provide the constant). We also relate the asymptotic distribution of another class of properties, which we call simple subtree additive properties, to the asymptotic distribution of the path length, both in the uniformly weighted case. The primary proof techniques in this paper come from analytic combinatorics, and most of our results follow from relating the moments of known and unknown distributions and showing that this is sufficient for convergence.
We consider the quantity $P(G)$ associated with a graph $G$ that is defined as the probability that a randomly chosen subtree of $G$ is spanning. Motivated by conjectures due to Chin, Gordon, MacPhee and Vincent on the behaviour of this graph invariant depending on the edge density, we establish first that $P(G)$ is bounded below by a positive constant provided that the minimum degree is bounded below by a linear function in the number of vertices. Thereafter, the focus is shifted to the classical ErdH{o}s-Renyi random graph model $G(n,p)$. It is shown that $P(G)$ converges in probability to $e^{-1/(ep_{infty})}$ if $p to p_{infty} > 0$ and to $0$ if $p to 0$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
