Functions on adjacent vertex degrees of trees with given degree sequence

In this note we consider a discrete symmetric function f(x, y) where $$f(x,a) + f(y,b) \geqslant f(y,a) + f(x,b) for any x \geqslant y and a \geqslant b,$$ associated with the degrees of adjacent vertices in a tree. The extremal trees with respect to the corresponding graph invariant, defined as $$\sum\limits_{uv \in E(T)} {f(deg(u),deg(v))} ,$$ are characterized by the “greedy tree” and “alternating greedy tree”. This is achieved through simple generalizations of previously used ideas on similar questions. As special cases, the already known extremal structures of the Randic index follow as corollaries. The extremal structures for the relatively new sum-connectivity index and harmonic index also follow immediately, some of these extremal structures have not been identified in previous studies.     

k-分支星状树的第二几何算术指标

数学化学中,第二几何算术指标是新近提出的一个图的拓扑指标,它与Szeged指标和点PI指标具有紧密关系.如果树的一个顶点υ的度大于等于3,则称顶点υ是其一个分支点.通过树的第二几何算术指标的一个增加或减少的变换,刻画了k-分支星状树的第二几何算术指标的最值,同时确定了相应的极图.     

Szeged index, edge Szeged index, and semi-star trees

A semi-star tree is a star tree whose some edges may be replaced by paths of length more than one. In this paper we present some increasing and decreasing transformations for Szeged index of the semi-star trees. Then we introduce palm semi-star tree and uniform semi-star tree and show that they are extremal with respect to the Szeged index and edge Szeged index. In addition, we investigate the relation between the Szeged index and edge Szeged index for all trees.     

On extremal indices greater than one for a scheme of series

The classic extremal index θ is an important parameter of asymptotic behavior of maxima of stationary random sequences. For applications, however, it is interesting to investigatemore complex structures. Recently, the extremal index was generalized to a scheme of series of random length. If the exact extremal index does not exist, then we consider partial indices. In contrast to the classic index, partial indices can be greater than one. In this paper, we consider a new model, where left and right partial indices can be greater than one and equal to each other, although the exact index does not exist.     

Atom-bond connectivity index of trees

The recently introduced atom-bond connectivity (ABC) index has been applied up to now to study the stability of alkanes and the strain energy of cycloalkanes. Here, mathematical properties of the ABC index of trees are studied. Chemical trees with extremal ABC values are found. In addition, it has been proven that, among all trees, the star tree, S_n, has the maximal ABC value.     

The Algebraic Connectivity of Graphs with Given Matching Number

The algebraic connectivity of a graph is the second smallest eigenvalue of the associated Laplacian matrix. In this paper, we not only characterize the extremal graphs with the maximal algebraic connectivity among all graphs of order n with given matching number, but also determine the extremal tree with the maximal algebraic connectivity among all trees of order n with given matching number.     

Wiener Index of Trees: Theory and Applications

The Wiener index W is the sum of distances between all pairs of vertices of a (connected) graph. The paper outlines the results known for W of trees: methods for computation of W and combinatorial expressions for W for various classes of trees, the isomorphism–discriminating power of W, connections between W and the center and centroid of a tree, as well as between W and the Laplacian eigenvalues, results on the Wiener indices of the line graphs of trees, on trees extremal w.r.t. W, and on integers which cannot be Wiener indices of trees. A few conjectures and open problems are mentioned, as well as the applications of W in chemistry, communication theory and elsewhere.     

固定直径的树的Wiener指数

图G的wiener指数定义为图中所有点对u,v的距离之和∑d（u,v）. 在这篇文章中,我们刻画了在n个顶点直径为d的所有树中具有第三小wiener指数的树的特征以及介绍了得到这类树的wiener指数排序的方法.     

The Number of Subtrees of Trees with Given Degree Sequence

This article investigates some properties of the number of subtrees of a tree with given degree sequence. These results are used to characterize trees with the given degree sequence that have the largest number of subtrees, which generalize the recent results of Kirk and Wang (SIAM J Discrete Math 22 (2008), 985–995). These trees coincide with those which were proven by Wang and independently Zhang et al. (2008) to minimize the Wiener index. We also provide a partial ordering of the extremal trees with different degree sequences, some extremal results follow as corollaries.     

Extremal indices, geometric ergodicity of Markov chains, and MCMC

We investigate the connections between extremal indices on the one hand and stability of Markov chains on the other hand. Both theories relate to the tail behaviour of stochastic processes, and we find a close link between the extremal index and geometric ergodicity. Our results are illustrated throughout with examples from simple MCMC chains.      

Laplacian coefficients of trees with given number of leaves or vertices of degree two

Let G be a simple undirected n-vertex graph with the characteristic polynomial of its Laplacian matrix . It is well known that for trees the Laplacian coefficient c_n-2 is equal to the Wiener index of G, while c_n-3 is equal to the modified hyper-Wiener index of graph. Using a result of Zhou and Gutman on the relation between the Laplacian coefficients and the matching numbers in subdivided bipartite graphs, we characterize the trees with k leaves (pendent vertices) which simultaneously minimize all Laplacian coefficients. In particular, this extremal balanced starlike tree S(n,k) minimizes the Wiener index, the modified hyper-Wiener index and recently introduced Laplacian-like energy. We prove that graph S(n,n-1-p) has minimal Laplacian coefficients among n-vertex trees with p vertices of degree two. In conclusion, we illustrate on examples of these spectrum-based invariants that the opposite problem of simultaneously maximizing all Laplacian coefficients has no solution, and pose a conjecture on extremal unicyclic graphs with k leaves.     

具有完美匹配树的代数连通度的排序

Jason等确定了阶数为n的具有完美匹配树的最大的代数连通度以及相应的极图．本文确定了阶数为n的具有完美匹配树的第二大到第五大的代数连通度以及达到这些数值的图（或图类）．     

On spanning tree problems with multiple objectives

We investigate two versions of multiple objective minimum spanning tree problems defined on a network with vectorial weights. First, we want to minimize the maximum ofQ linear objective functions taken over the set of all spanning trees (max-linear spanning tree problem, ML-ST). Secondly, we look for efficient spanning trees (multi-criteria spanning tree problem, MC-ST).Problem ML-ST is shown to be NP-complete. An exact algorithm which is based on ranking is presented. The procedure can also be used as an approximation scheme. For solving the bicriterion MC-ST, which in the worst case may have an exponential number of efficient trees, a two-phase procedure is presented. Based on the computation of extremal efficient spanning trees we use neighbourhood search to determine a sequence of solutions with the property that the distance between two consecutive solutions is less than a given accuracy.Partially supported by Deutsche Forschungsgemeinschaft and HCº Contract no. ERBCHRXCT 930087.Partially supported by Alexander von Humboldt-Stiftung.     

The extremal index,hitting time statistics and periodicity

The extremal index appears as a parameter in Extreme Value Laws for stochastic processes, characterising the clustering of extreme events. We apply this idea in a dynamical systems context to analyse the possible Extreme Value Laws for the stochastic process generated by observations taken along dynamical orbits with respect to various measures. We derive new, easily checkable, conditions which identify Extreme Value Laws with particular extremal indices. In the dynamical context we prove that the extremal index is associated with periodic behaviour. The analogy of these laws in the context of hitting time statistics, as studied in the authors’ previous works on this topic, is explained and exploited extensively allowing us to prove, for the first time, the existence of hitting time statistics for balls around periodic points. Moreover, for very well behaved systems (uniformly expanding) we completely characterise the extremal behaviour by proving that either we have an extremal index less than 1 at periodic points or equal to 1 at any other point. This theory then also applies directly to general stochastic processes, adding both useful tools to identify the extremal index and giving deeper insight into the periodic behaviour it suggests.     

The continuum random tree is the scaling limit of unlabeled unrooted trees

We show that the uniform unlabeled unrooted tree with n vertices and vertex degrees in a fixed set converges in the Gromov‐Hausdorff sense after a suitable rescaling to the Brownian continuum random tree. This confirms a conjecture by Aldous (1991). We also establish Benjamini‐Schramm convergence of this model of random trees and provide a general approximation result, that allows for a transfer of a wide range of asymptotic properties of extremal and additive graph parameters from Pólya trees to unrooted trees.     

Simulation study of dissimilarity between point process

The spatial distributions of two species of tree result in a bivariate pattern. This pattern characterizes biological mechanism involved within a forest with the spatial localization of the trees. If we consider simultaneously two species, the main question is not to describe the marginal distribution of each species but to describe the relationship between the repartitions of the two species under study. The relationship between two clouds of points can be described in various ways and therefore many indices can be defined. Each index will give a specific information about these relationships and will greatly depends on the ecological mechanisms, i.e., the point process that leads to the observed repartition. The aim of this article is to review the leading indices in ecology and to provide guidelines for practical use. To mimic ecological situations, we simulated 13 point process that can model classical relationships between two species of trees and compute nine classical indices. The interest of the various indices are discussed. A R package for simulating the point process and to compute the indices is available on request. The package is available upon request at picard@cirad.fr or avner@inapg.fr