اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدPerron value and moment of rooted trees
125
0
0.0
(
0
)
تأليف
Lorenzo Ciardo
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The Perron value $rho(T)$ of a rooted tree $T$ has a central role in the study of the algebraic connectivity and characteristic set, and it can be considered a weight of spectral nature for $T$. A different, combinatorial weight notion for $T$ - the moment $mu(T)$ - emerges from the analysis of Kemenys constant in the context of random walks on graphs. In the present work, we compare these two weight concepts showing that $mu(T)$ is almost an upper bound for $rho(T)$ and the ratio $mu(T)/rho(T)$ is unbounded but at most linear in the order of $T$. To achieve these primary goals, we introduce two new objects associated with $T$ - the Perron entropy and the neckbottle matrix - and we investigate how different operations on the set of rooted trees affect the Perron value and the moment.
قيم البحث
اقرأ أيضاً
We introduce some natural families of distributions on rooted binary ranked plane trees with a view toward unifying ideas from various fields, including macroevolution, epidemiology, computational group theory, search algorithms and other fields. In
the process we introduce the notions of split-exchangeability and plane-invariance of a general Markov splitting model in order to readily obtain probabilities over various equivalence classes of trees that arise in statistics, phylogenetics, epidemiology and group theory.
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.
The modular decomposition of a symmetric map $deltacolon Xtimes X to Upsilon$ (or, equivalently, a set of symmetric binary relations, a 2-structure, or an edge-colored undirected graph) is a natural construction to capture key features of $delta$ in
labeled trees. A map $delta$ is explained by a vertex-labeled rooted tree $(T,t)$ if the label $delta(x,y)$ coincides with the label of the last common ancestor of $x$ and $y$ in $T$, i.e., if $delta(x,y)=t(mathrm{lca}(x,y))$. Only maps whose modular decomposition does not contain prime nodes, i.e., the symbolic ultrametrics, can be exaplained in this manner. Here we consider rooted median graphs as a generalization to (modular decomposition) trees to explain symmetric maps. We first show that every symmetric map can be explained by extended hypercubes and half-grids. We then derive a a linear-time algorithm that stepwisely resolves prime vertices in the modular decomposition tree to obtain a rooted and labeled median graph that explains a given symmetric map $delta$. We argue that the resulting tree-like median graphs may be of use in phylogenetics as a model of evolutionary relationships.
In this paper we enumerate the cardinalities for the set of all vertices of outdegree $ge k$ at level $ge ell$ among all rooted ordered $d$-trees with $n$ edges. Our results unite and generalize several previous works in the literature.
In this paper we enumerate and give bijections for the following four sets of vertices among rooted ordered trees of a fixed size: (i) first-children of degree $k$ at level $ell$, (ii) non-first-children of degree $k$ at level $ell-1$, (iii) leaves h
aving $k-1$ elder siblings at level $ell$, and (iv) non-leaves of outdegree $k$ at level $ell-1$. Our results unite and generalize several previous works in the literature.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
