树的Nordhaus-Gaddum类型谱半径的排序

给出了n阶树的Nordhaus-Gaddum类型谱半径即图及其补图的谱半径之和的可达上界:ρ(T) ρ(Tc)≤■ n-2,等号成立当且仅当T K1,n-1,其中Tc为T的补图,K1,n-1为n阶星图.同时证明了对于n阶双星图S(a,b)的Nordhaus-Gaddum类型谱半径随a的值单调上升,其中[n-1/2]≤a≤n-3.     

树的3-彩虹控制数的上界

对树的3-彩虹控制数进行研究,首先用构造法找到直径较小的树的3-彩虹控制数的上界.再通过分类讨论思想和数学归纳法得到一般的阶n大于等于5的树的3-彩虹控制数的上界.     

树的第二大特征值的界

在文献Ji-Ming Guo,Shang-Wang Tan.A conjecture on the second largest eigenvalue of a tree with perfect matchings.Linear Algebra and its Applications,2002,347(1-3):9-15和Ji-Ming Guo,Shang-Wang Tan.A note on the second largest eigenvalue of a tree with perfect matchings.Linear Algebra and Its Applications,2004,380:125-134中,Guo和Tan给出了有2k个顶点且有完美匹配的树的第二大特征值的上界,这个上界与顶点数有关,并且刻画了第二大特征值达到该上界的树.本文给出了有2k个顶点的树的第二大特征值的上界,这个上界与顶点数和最大匹配的基数有关,并且刻画了第二大特征值达到该上界的树.     

树的几何反比度上界

设G(V,E)是一个任意图，定义为G的几何反比度，本文证明了，其中T为顶点数为n的树，这个上界值是精确的     

几类树的无矛盾点连通数

本论文研究了点着色图的无矛盾点连通数的问题,利用树的结构特征获得了特殊图类Τ_(n,k)关于无矛盾点连通数的上界和下界,Τ_(n)^(A)、T_(A)和A_(d)关于无矛盾点连通数的上界.     

一类二次可逆系统的Abel积分

利用Picard-Fuchs方程法及Riccati方程法,研究了一类二次可逆系统在任意n次多项式扰动下Abel积分零点个数的上界问题,得到了当n≥4时,上界为10n+[n/2]-1.     

围长为r的n阶本原有向图的点指数

研究本原有向图的顶点指数,运用图论与数论方法,得到了n阶围长为r的本原有向图的点指数expD（k）的上界：若rn,且r为素数,D∈Dn,r={D｜D为n阶本原有向图且围长为r},则expD（n,k）=rn-2r＋k（1≤k≤n）;若r｜n,且r为素数或素数的幂,D∈Dn,r,则expD（n,1）=rn-3r＋2.     

三路树P（m,n,t）是边幼图的证明

[1]中猜测每一树是边幼图,本证明了三路树P（m,n,t)当（i)n,t为偶数且相等,（ii)t=n 1,(iii)n为奇数且t=n 2时为边幼图。     

最优布尔函数的一个性质

Walsh谱只有3个值:0,±2m+2,且同时达到代数次数上界n-m-1和非线性度上界2n-1-2m+1的n元m阶弹性布尔函数(m>n/2-2)称为饱和最优函数(saturatedbest简写为SB).本文将给出关于SB函数非零谱值位置分布的一个性质,利用这一性质我们给出构造非线性度为56的4次7兀2阶弹性布尔函数的一种方法.     

方程(dx/dt)=x~n sum from i=0 to (n-1) a_i(t)x~2的闭解的个数及存在的条件

本文给出方程n＝3时分别正好存在1个闭解，3个闭解，以及至少存在2个闭解的充分条件，并研究了这些闭解的稳定性．当n＝4且ai（t）（i＝0，1，2，3）为t的P次多项式时，文[1]曾猜想其时闭解重数的上界为max｛4，p＋3｝．本文举例指出，即使p＝3，闭解重数的上界也可以大于7．这说明该猜想不成立     

Height-analysis ofk-dimensional leaf and node height-balanced trees: A new approach

A new general approach is proposed for the height-analysis ofk-dimensional leaf and node height-balanced trees which is expected to be useful for such analysis of other neighbor-supported balanced multidimensional trees as well. The approach leads to upper bounds which are the same as the known upper bounds for the corresponding 1-dimensional trees, to within an additive term.This research is partially supported by a grant from the College of Business Administration, Georgia State University, Atlanta, Georgia.Actually a variant calledalmost 2-dimensional leaf AVL-trees is introduced in order to facilitate the derivation of an upper bound for the height of these trees which is within an additive term to the bound for such 1-dimensional trees.     

New upper bounds on the spectral radius of trees with the given number of vertices and maximum degree

This paper studies the problem of estimating the spectral radius of trees with the given number of vertices and maximum degree. We obtain the new upper bounds on the spectral radius of the trees, and the results are the best upper bounds expressed by the number of vertices and maximum degree, at present.     

Upper and Lower Bounds for the Lengths of Steiner Trees in 3-Space

We present a method of determining upper and lower bounds for the length of a Steiner minimal tree in 3-space whose topology is a given full Steiner topology, or a degenerate form of that full Steiner topology. The bounds are tight, in the sense that they are exactly satisfied for some configurations. This represents the first nontrivial lower bound to appear in the literature. The bounds are developed by first studying properties of Simpson lines in both two and three dimensional space, and then introducing a class of easily constructed trees, called midpoint trees, which provide the upper and lower bounds. These bounds can be constructed in quadratic time. Finally, we discuss strategies for improving the lower bound.Supported by a grant from the Australia Research Council.     

给定阶与边独立数的树和单圈图的Laplacian矩阵的最大特征值

得到了给定顶点数和边独立数的树与单圈图的Laplacian矩阵的最大特征值的精确上界，并且给出了达到上界的所有极图．     

Lagrangean bounds for the optimum communication spanning tree problem

This paper considers the Optimum Communication Spanning Tree Problem. An integer programming formulation that yields tight LP bounds is proposed. Given that the computational effort required to obtain the LP bounds considerably increases with the size of the instances when using commercial solvers, we propose a Lagrangean relaxation that exploits the structure of the formulation. Since feasible solutions to the Lagrangean function are spanning trees, upper bounds are also obtained. These bounds are later improved with a simple local search. Computational experiments have been run on several benchmark instances from the literature. The results confirm the interest of the proposal since tight lower and upper bounds are obtained, for instances up to 100 nodes, in competitive computational times.     

Extremal first passage times for trees

For random walks associated with trees with probability zero of staying at any vertex, we develop explicit graph theoretic formulas for the mean first passage times between states, we give lower and upper bounds for the entries of the mean first passage matrix E, and we characterize the cases of equality in these bounds. We also consider the variance of the first return time to a state and we find those trees which maximize the variance and those trees which minimize the variance. As may be expected, the trees which provide extremal behavior are given by paths and stars.     

Ratios of some domination parameters in trees

We determine upper bounds on the ratios of several domination parameters in trees.     

Upper bounds for the associated number of zeros of Abelian integrals for two classes of quadratic reversible centers of genus one

In this paper, by using the method of Picard-Fuchs equation and Riccati equation, we study the upper bounds for the associated number of zeros of Abelian integrals for two classes of quadratic reversible centers of genus one under any polynomial perturbations of degree $n$, and obtain that their upper bounds are $3n-3$ ($n\geq 2$) and $18\left[\frac{n}{2}\right]+3\left[\frac{n-1}{2}\right]$ ($n\geq 4$) respectively, both of the two upper bounds linearly depend on $n$.     

对于K2+Tm和完全图的Ramsey函数的渐近上界

本文研究了当n趋于无穷大时,关于K2+Tm和完全图Kn的Ramsey数的渐近上界,以及r(K2+Tm,Kn)和r(K1+Tm,Kn)的渐近关系.利用李雨生等人所给出的一个独立数的下界公式,给出了r(K4,Kn)和r(Kk-c,Kn)的渐近上下界,推广了李雨生等人所给出的r(K1+Tm,Kn)的下界.