共查询到20条相似文献,搜索用时 44 毫秒
1.
2.
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 with maximum mean subtree order must be very close to . Moreover, we show that the maximum mean subtree order is equal to . 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 . 相似文献
3.
4.
Magnus Bordewich Catherine McCartin Charles Semple 《Journal of Discrete Algorithms》2008,6(3):458-471
In this paper, we give a (polynomial-time) 3-approximation algorithm for the rooted subtree prune and regraft distance between two phylogenetic trees. This problem is known to be NP-complete and the best previously known approximation algorithm is a 5-approximation. We also give a faster fixed-parameter algorithm for the rooted subtree prune and regraft distance than was previously known. 相似文献
5.
In this paper we establish new characterization results concerning horospheres of the hyperbolic space under certain appropriate constraints in the behavior of the higher order mean curvatures. Our approach is based on a suitable maximum principle for complete Riemannian manifolds. Moreover, we present examples showing the importance of the main hypothesis of our results. 相似文献
6.
Comparisons in the mean residual life order of coherent systems with identically distributed components
下载免费PDF全文
![点击此处可从《商业与工业应用随机模型》网站下载免费的PDF全文](/ch/ext_images/free.gif)
The comparisons of the performance of coherent systems (under different stochastic criteria) is an important task in the reliability theory. Several results have been obtained in the literature for the stochastic, hazard rate and likelihood ratio orders. In this paper, we obtain comparison results for the mean residual life order of coherent systems with identically distributed (ID) component lifetimes. These results can be applied not only to the usual case of systems with independent and identically distributed components but also to the case of systems with exchangeable components and to the more general case of just ID components. The results obtained are based on the representation of the system distribution as a distorted distribution of the common components' distribution. Some specific comparison results are given to illustrate the theoretical results. The comparison results for distorted distributions given here can also be applied to other statistical concepts such as order statistics, generalized order statistics or record values. Copyright © 2015 John Wiley & Sons, Ltd. 相似文献
7.
In this paper,we establish the first variational formula and its Euler-Lagrange equation for the total 2p-th mean curvature functional M2p of a submanifold M n in a general Riemannian manifold N n+m for p = 0,1,...,[n 2 ].As an example,we prove that closed complex submanifolds in complex projective spaces are critical points of the functional M2p,called relatively 2p-minimal submanifolds,for all p.At last,we discuss the relations between relatively 2p-minimal submanifolds and austere submanifolds in real space forms,as well as a special variational problem. 相似文献
8.
Danny Hermelin 《Discrete Applied Mathematics》2011,159(7):588-594
We study various optimization problems in t-subtree graphs, the intersection graphs of t-subtrees, where a t-subtree is the union of t disjoint subtrees of some tree. This graph class generalizes both the class of chordal graphs and the class of t-interval graphs, a generalization of interval graphs that has recently been studied from a combinatorial optimization point of view. We present approximation algorithms for the Maximum Independent Set, Minimum Coloring, Minimum Vertex Cover, Minimum Dominating Set, and Maximum Clique problems. 相似文献
9.
Maximal elements of a binary relation on compact subsets of a metric space define a choice function. An infinite extension of transitivity is necessary and sufficient for such a choice function to be nonempty-valued and path independent (or satisfy the outcast axiom). An infinite extension of acyclicity is necessary and sufficient for the choice function to have nonempty values provided the underlying relation is an interval order. 相似文献
10.
Andrzej ?ak 《Discrete Mathematics》2009,309(20):6055-6064
We consider the following generalization of the concept of harmonious graphs. Given a graph G=(V,E) and a positive integer t≥|E|, a function is called a t-harmonious labeling of G if is injective for t≥|V| or surjective for t<|V|, and for all distinct edges vw,xy∈E(G). Then the smallest possible t such that G has a t-harmonious labeling is named the harmonious order of G. We determine the harmonious order of some non-harmonious graphs, such as complete graphs Kn (n≥5), complete bipartite graphs Km,n (m,n>1), even cycles Cn, some powers of paths , disjoint unions of triangles nK3 (n even). We also present some general results concerning harmonious order of the Cartesian product of two given graphs or harmonious order of the disjoint union of copies of a given graph. Furthermore, we establish an upper bound for harmonious order of trees. 相似文献
11.
Motivated by the theory of isoparametric hypersurfaces,we study submanifolds whose tubular hypersurfaces have some constant higher order mean curvatures.Here a k-th order mean curvature Q_k~v(k ≥ 1) of a submanifold M~n-is defined as the k-th power sum of the principal curvatures,or equivalently,of the shape operator with respect to the unit normal vector v.We show that if all nearby tubular hypersurfaces of M have some constant higher order mean curvatures,then the submanifold M itself has some constant higher order mean curvatures Q_k~v independent of the choice of v.Many identities involving higher order mean curvatures and Jacobi operators on such submanifolds are also obtained.In particular,we generalize several classical results in isoparametric theory given by E.Cartan,K.Nomizu,H.F.Miinzner,Q.M.Wang,et al.As an application,we finally get a geometrical filtration for the focal submanifolds of isoparametric functions on a complete Riemannian manifold. 相似文献
12.
We study hypersurfaces in Euclidean space
whose position vector x satisfies the condition L
k
x = Ax + b, where L
k
is the linearized operator of the (k + 1)th mean curvature of the hypersurface for a fixed
,
is a constant matrix and
is a constant vector. For every k, we prove that the only hypersurfaces satisfying that condition are hypersurfaces with zero (k + 1)th mean curvature and open pieces of round hyperspheres and generalized right spherical cylinders of the form
, with
. This extends a previous classification for hypersurfaces in
satisfying
, where
is the Laplacian operator of the hypersurface, given independently by Hasanis and Vlachos [J. Austral. Math. Soc. Ser. A
53, 377–384 (1991) and Chen and Petrovic [Bull. Austral. Math. Soc. 44, 117–129 (1991)].
相似文献
13.
LI Yong-min WANG Miao-kun CHU Yu-ming 《高校应用数学学报(英文版)》2014,29(1):101-107
In this paper,we find the greatest value p = log2/(log π. log 2) = 1.53 ··· and the least value q = 5/3 = 1.66 ··· such that the double inequality Mp(a,b) T(a,b) Mq(a,b) holds for all a,b 0 with a = b. Here,Mp(a,b) and T(a,b) are the p-th power and Seiffert means of two positive numbers a and b,respectively. 相似文献
14.
For p ∈ R, the generalized logarithmic mean Lp(a,b) and Seiffert's mean T(a,b) of two positive real numbers a and b are defined in (1.1) and (1.2) below respectively. In this paper, we find the greatest p and least q such that the double-inequality Lp(a,b) < T(a,b) < Lq(a,b) holds for all a,b > 0 and a ≠ b. 相似文献
15.
Let T be any tree of order d≥1. We prove that every connected graph G with minimum degree d contains a subtree T′ isomorphic to T such that G−V(T′) is connected. 相似文献
16.
The purpose of this research is to present a novel scheme based on a quick iterative scheme for calculating the matrix geometric mean of two Hermitian positive definite (HPD) matrices. To do this, an iterative scheme with global convergence is constructed for the sign function using a novel three‐step root‐solver. It is proved that the new scheme is convergent and shown to have global convergence behavior for this target, when square matrices having no pure imaginary eigenvalues. Next, the constructed scheme is used and extended through a well‐known identity for the calculation of the matrix geometric mean of two HPD matrices. Ultimately, several experiments are collected to show its usefulness. 相似文献
17.
Mohamed Ben Ayed 《Journal of Functional Analysis》2010,258(9):3165-3194
In this article we consider the following fourth order mean field equation on smooth domain Ω?R4:
18.
Given a tree with n nodes, we consider the problem of finding the most profitable subtree of that tree with at most K nodes which is known as the Cardinality Subtree of a Tree Problem. We present a new exact linear extended formulation with O(nK) two-indexed variables and O(nK) constraints. 相似文献
19.
《Discrete Mathematics》2019,342(1):152-167
We address questions of logic and expressibility in the context of random rooted trees. Infiniteness of a rooted tree is not expressible as a first order sentence, but is expressible as an existential monadic second order sentence (EMSO). On the other hand, finiteness is not expressible as an EMSO. For a broad class of random tree models, including Galton–Watson trees with offspring distributions that have full support, we prove the stronger statement that finiteness does not agree up to a null set with any EMSO. We construct a finite tree and a non-null set of infinite trees that cannot be distinguished from each other by any EMSO of given parameters. This is proved via set-pebble Ehrenfeucht games (where an initial colouring round is followed by a given number of pebble rounds). 相似文献
20.
陈乃辉 《纯粹数学与应用数学》2008,24(2)
在随机函数的环境下,推广了经典函数逼近论中的Jackson逼近阶定理.建立了随机函数均方连续模的概念,并得到其有关性质后,研究了四种不同条件下随机函数被随机系数三角多项式逼近的阶之估计. 相似文献