On the maximum mean subtree order of trees

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-2{log}_{2}n+O\left(1\right)$. 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\left(1\right)$.     

A 3-approximation algorithm for the subtree distance between phylogenies

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.     

Characterizing horospheres of the hyperbolic space via higher order mean curvatures

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.     

Comparisons in the mean residual life order of coherent systems with identically distributed components

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.     

Variational formulas of higher order mean curvatures

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.     

Optimization problems in multiple subtree graphs

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.     

Maximizing an interval order on compact subsets of its domain

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.     

Harmonious order of graphs

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 K_n (n≥5), complete bipartite graphs K_m,n (m,n>1), even cycles C_n, some powers of paths , disjoint unions of triangles nK₃ (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.     

On submanifolds whose tubular hypersurfaces have constant higher order mean curvatures

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.     

An extension of Takahashi theorem for the linearized operators of the higher order mean curvatures

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)].      

Sharp power mean bounds for Sei?ert mean简

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.     

The optimal generalized logarithmic mean bounds for Seiffert's mean

For p ∈ R, the generalized logarithmic mean L_p(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 L_p(a,b) < T(a,b) < L_q(a,b) holds for all a,b > 0 and a ≠ b.     

Non-separating trees in connected graphs

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.     

A fast iterative method to find the matrix geometric mean of two HPD matrices

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.     

Existence and multiplicity results for a fourth order mean field equation

In this article we consider the following fourth order mean field equation on smooth domain Ω?R⁴:

     

Extended formulations for the cardinality constrained subtree of a tree problem

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.     

Existential monadic second order logic on random rooted trees

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).     

推广Jackson逼近阶定理

在随机函数的环境下,推广了经典函数逼近论中的Jackson逼近阶定理.建立了随机函数均方连续模的概念,并得到其有关性质后,研究了四种不同条件下随机函数被随机系数三角多项式逼近的阶之估计.