Searching in trees

In (Discrete Math. 17 (1977)181) Rivest introduced the search complexity of binary trees and proved that among all binary trees with a fixed search complexity the smallest ones are the so-called Fibonacci trees. This result is extended for q-trees. The structure of the smallest q-trees is again Fibonacci-like but more complicated than in the binary case. In addition an upper bound for the asymptotic growth of these trees is given.     

Stability Conditions of the MMAP [ K ]/ G [ K ]/1/ LCFS Preemptive Repeat Queue

In this paper, we study the stability conditions of the MMAP[K]/G[K]/1/LCFS preemptive repeat queue. We introduce an embedded Markov chain of matrix M/G/1 type with a tree structure and identify conditions for the Markov chain to be ergodic. First, we present three conventional methods for the stability problem of the queueing system of interest. These methods are either computationally demanding or do not provide accurate information for system stability. Then we introduce a novel approach that develops two linear programs whose solutions provide sufficient conditions for stability or instability of the queueing system. The new approach is numerically efficient. The advantages and disadvantages of the methods introduced in this paper are analyzed both theoretically and numerically.     

Degree-regular triangulations of torus and Klein bottle

A triangulation of a connected closed surface is called weakly regular if the action of its automorphism group on its vertices is transitive. A triangulation of a connected closed surface is called degree-regular if each of its vertices have the same degree. Clearly, a weakly regular triangulation is degree-regular. In [8], Lutz has classified all the weakly regular triangulations on at most 15 vertices. In [5], Datta and Nilakantan have classified all the degree-regular triangulations of closed surfaces on at most 11 vertices. In this article, we have proved that any degree-regular triangulation of the torus is weakly regular. We have shown that there exists ann-vertex degree-regular triangulation of the Klein bottle if and only if n is a composite number ≥ 9. We have constructed two distinctn-vertex weakly regular triangulations of the torus for eachn ≥ 12 and a (4m + 2)-vertex weakly regular triangulation of the Klein bottle for eachm ≥ 2. For 12 ≤n ≤ 15, we have classified all then-vertex degree-regular triangulations of the torus and the Klein bottle. There are exactly 19 such triangulations, 12 of which are triangulations of the torus and remaining 7 are triangulations of the Klein bottle. Among the last 7, only one is weakly regular.     

Nowhere zero 4‐flow in regular matroids

Jensen and Toft 8 conjectured that every 2‐edge‐connected graph without a K₅‐minor has a nowhere zero 4‐flow. Walton and Welsh 19 proved that if a coloopless regular matroid M does not have a minor in {M(K_3,3), M*(K₅)}, then M admits a nowhere zero 4‐flow. In this note, we prove that if a coloopless regular matroid M does not have a minor in {M(K₅), M*(K₅)}, then M admits a nowhere zero 4‐flow. Our result implies the Jensen and Toft conjecture. © 2005 Wiley Periodicals, Inc. J Graph Theory     

浙江中部夏熟作物田主要杂草生态相似性的数量分析

应用七级目测法对浙江中部地区27个夏熟作物田样点的杂草进行了优势等级调查，将所得数据转换成重要值，以杂草在27个样点中的重要值为运算指标，应用主成分分析法和图论聚类中的最小生成树法，对24种杂草的生态学相似性进行了比较，指出了长期使用单一的除草剂导致农田杂草种群迅速更迭的原因：杂草对除草剂的敏感性差异及不同杂草间的生态学特性的差异。     

Parametric multiple sequence alignment and phylogeny construction

Bounds are given on the size of the parameter-space decomposition induced by multiple sequence alignment problems where phylogenetic information may be given or inferred. It is shown that many of the usual formulations of these problems fall within the same integer parametric framework, implying that the number of distinct optima obtained as the parameters are varied across their ranges is polynomially bounded in the length and number of sequences.     

Automorphisms of Green Orders and Their Derived Categories

In an earlier paper, Raphaël Rouquier and the author introduced the group of self-equivalences of a derived category. In the case of a Brauer tree algebra, we determined a nontrivial homomorphism of the Artin braid group to this group of self-equivalences. The class of Brauer tree algebras include blocks of finite group rings over a large enough field with cyclic defect groups. In the present paper we give an integral version of this homomorphism. Moreover, we identify some interesting arithmetic subgroups with natural groups of self-equivalences of the derived category.     

A Note on Cactus Trees: Variational vs. Recursive Approach

In this article we deal with the variational approach to cactus trees (Husimi trees) and the more common recursive approach, that are in principle equivalent for finite systems. We discuss in detail the conditions under which the two methods are equivalent also in the analysis of infinite (self-similar) cactus trees, usually investigated to the purpose of approximating ordinary lattice systems. Such issue is hardly ever considered in the literature. We show (on significant test models) that the phase diagram and the thermodynamic quantities computed by the variational method, when they deviates from the exact bulk properties of the cactus system, generally provide a better approximation to the behavior of a corresponding ordinary system. Generalizing a property proved by Kikuchi, we also show that the numerical algorithm usually employed to perform the free energy minimization in the variational approach is always convergent.