双圈图的Laplace谱跨度

The Laplacian spread of a graph is defined to be the difference between the largest eigenvalue and the second smallest eigenvalue of the Laplacian matrix of the graph. In our recent work, we have determined the graphs with maximal Laplacian spreads among all trees of fixed order and among all unicyclic graphs of fixed order, respectively. In this paper, we continue the work on Laplacian spread of graphs, and prove that there exist exactly two bicyclic graphs with maximal Laplacian spread among all bicyclic graphs of fixed order, which are obtained from a star by adding two incident edges and by adding two nonincident edges between the pendant vertices of the star, respectively.     

LINE COLORED TREES WITH EXTENDABLE AUTOMORPHISMS

An E-tree is a rooted line-colored tree such that every automorphism of a subtree contain-s ing the root can be extended to an automorphism of the entire tree. When only one color i used, E-trees correspond both to achiral planted trees and to partitions with successively divisible parts. The exact numbers of E-trees with n points and colors from a store of c are found, with and without the restriction that each color should be used at least one. Asymptotic formulas for these quantities are discussed for c fixed and n→∞.     

SOME COMBINATORIAL PROBLEMS ON ORDERED TREES

Some formulas are established to calculate the number of leaves on all structurallydifferent ordered trees with n nodes,and the total leaf path length and the total node pathlength for those trees.Certainly,respective average numbers are obtained(the average pathlength may be considered as the average height of random ordered trees with n nodes),Actually,this paper presents a general method dealing with some classes of combinaorialproblems on ordered trees.     

用拉普拉斯谱半径定序给定阶和匹配数的树

Let T（n,i） be the set of all trees with order n and matching number i.We determine the third to sixth trees in T（2i ＋ 1,i） and the third to fifth trees in T（n,i） for n ≥ 2i ＋ 2 with the largest Laplacian spectral radius.     

AN ENUMERATION PROBLEM ON t-ARY TREES

In this paper, an enumeration problem on t-ary trees with m interior nodes and n leaves is discussed. In the analysis of algorithms over tree structures, it is not sufficient to consider roughly the behavior of algorithms over trees with m nodes, because the difference between the structures of the two different trees with m nodes may be great. However, on the other hand, the difference between the structures of the trees with m interior nodes and n leaves may be relatively small. Thus, in such an analysis, it is needed to count the number of struc-     

Ordering trees by their spectral radii

Let T be a tree with n vertices and let A（T） be the adjacency matrix of T. Spectral radius of T is the largest eigenvalue of A（T）. Wu et al. [Wu, B.F., Yuan, X.Y, and Xiao, E.L. On the spectral radii of trees, Journal of East China Normal University （Natural Science）, 3：22-28 （2004）] determined the first seven trees of order n with the smallest spectral radius. In this paper, we extend this ordering by determining the trees with the eighth to the tenth smallest spectral radius among all trees with n vertices.     

Depth in bucket recursive trees with variable capacities of buckets

We consider bucket recursive trees of sizen consisting of all buckets with variable capacities1,2,...,b and with a specifc stochastic growth rule.This model can be considered as a generalization of random recursive trees like bucket recursive trees introduced by Mahmoud and Smythe where all buckets have the same capacities.In this work,we provide a combinatorial analysis of these trees where the generating function of the total weights satisfes an autonomous frst order diferential equation.We study the depth of the largest label（i.e.,the number of edges from the root node to the node containing label n）and give a closed formula for the probability distribution.Also we prove a limit law for this quantity which is a direct application of quasi power theorem and compute its mean and variance.Our results for b=1 reduce to the previous results for random recursive trees.     

TREES MAPPING PRINCIPLE

This papar exploits a number of problems associated with the trees mapping, has put forward a universal set of the tree data structure defined on an arbitrary finite integeral domain and has studied the character of the set which will be studied further in [5].For the first time. it advences a mathematical expression on trees, and on the basis of the expression, has more deeply studied the boundary character for a trees mapping, So that an analytic expression on a geometric parameter pair (p. w) has been established.In the last section, this papar has established a more general expanding relation on the data structure and defined a number of important ideas associated with data elements, So that it has profoundly exposed the structure character on trees.     

Motzkin树上的保护点的计数问题

In this paper,we enumerate the set of Motzkin trees with n edges according to the number of leaves,the number of vertices adjacent to a leaf,the number of protected nodes,the number of(protected)branch nodes,and the number of(protected)lonely nodes.Explicit formulae as well as generating functions are obtained.We also find that,as n goes to infinity,the proportion of protected branch nodes and protected lonely nodes among all vertices of Motzkin trees with n edges approaches 4/27 and 2/9.     

无穷时滞的泛函微分方程的多重正周期解(英文)

In this paper, we investigate the existence of multiple positive periodic solutions for functional differential equations with infinite delay by applying the Krasnoselskii fixed point theorem for cone map and the Leggett-Williams fixed point theorem.     

Enumerating spanning trees of graphs with an involution

As the extension of the previous work by Ciucu and the present authors [M. Ciucu, W.G. Yan, F.J. Zhang, The number of spanning trees of plane graphs with reflective symmetry, J. Combin. Theory Ser. A 112 (2005) 105-116], this paper considers the problem of enumeration of spanning trees of weighted graphs with an involution which allows fixed points. We show that if G is a weighted graph with an involution, then the sum of weights of spanning trees of G can be expressed in terms of the product of the sums of weights of spanning trees of two weighted graphs with a smaller size determined by the involution of G. As applications, we enumerate spanning trees of the almost-complete bipartite graph, the almost-complete graph, the Möbius ladder, and the almost-join of two copies of a graph.     

Integral trees of odd diameters

A graph is called integral if all eigenvalues of its adjacency matrix consist entirely of integers. Recently, Csikvári proved the existence of integral trees of any even diameter. In the odd case, integral trees have been constructed with diameter at most 7. In this article, we show that for every odd integer n>1, there are infinitely many integral trees of diameter n. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Implicit construction of multiple eigenvalues for trees

We are generally concerned with the possible lists of multiplicities for the eigenvalues of a real symmetric matrix with a given graph. Many restrictions are known, but it is often problematic to construct a matrix with desired multiplicities, even if a matrix with such multiplicities exists. Here, we develop a technique for construction using the implicit function theorem in a certain way. We show that the technique works for a large variety of trees, give examples and determine all possible multiplicities for a large class of trees for which this was not previously known.     

树的第二个最大特征值

本文得到了边独立数为n且阶为2n+2的树的第二个最大特征值的精确上界,且给出了达到上界的所有的极树.     

On Trees Whose Second Largest Eigenvalue Does Not Exceed 1

1.IntroductionLetGbeasimplegraphandA(G)betheadjacencymatrixofagraphGwithnvenices.ThecharacteristicpolynomialofGisthecharacteristicpolynomialofitsadjacencymatriX,denotedbyP(G;A),henceP(G;A)=det(AI--A(G)).SinceA(G)isarealsymmeticmatrix,itseigenvaluesmustberealandorderedasThoseAl(A(G))arecalleditheigenvalueofG,denotedAl(A(G))byAl(G).ThereareinseparableconnectionbetweentheconstructionandtheeigenvalueofgraphG.Severalbooksandalotofliterariesoneigenvaluesofgraphsanditsapplicationhavebeenp…     

双圈图的Laplacian Spread(英文)

Laplacian spread的概念在刻画图的整体性质方面非常重要.近年来,Fan等分别刻画了树中具有极大和极小Laplacian spread的图.另外Bao等确定了在所有单圈图中具有极大Laplacian spread的图.边数减去顶点数目为1的连通图称为双圈图.令B_n是所有有n个顶点构成的双圈图集合.对n≥11,本文确定了B_n中所有具有极大Laplacian spread的那些图.     

Trees with minimal index and diameter at most four

In this paper we consider the trees with fixed order n and diameter d≤4. Among these trees we identify those trees whose index is minimal.     

On the Laplacian spectral radius of weighted trees with a positive weight set

The spectrum of weighted graphs is often used to solve the problems in the design of networks and electronic circuits. We first give some perturbational results on the (signless) Laplacian spectral radius of weighted graphs when some weights of edges are modified; we then determine the weighted tree with the largest Laplacian spectral radius in the set of all weighted trees with a fixed number of pendant vertices and a positive weight set. Furthermore, we also derive the weighted trees with the largest Laplacian spectral radius in the set of all weighted trees with a fixed positive weight set and independence number, matching number or total independence number.     

树上生灭过程的Dirichlet特征值估计

本文给出树上两类非常返的生灭过程的第一Dirichlet特征值的变分公式．一类是配称测度有限时,给出以根为吸收点的Dirichlet特征值的变分公式;另一类是配称测度无限时,给出树上生灭过程的Dirichlet主特征值的变分公式．