(m,n)-树的几个判定条件

通过构造(m,n)-树的(m,n)-图,给出了判断(m,n)-树的几个充分必要条件,从而进一步揭示了(m,n)-树的结构特征。     

(m,n)-树的一个充分必要条件

通过在(m,n)-树中引入Graham约化过程,给出了(m,n)-树的一个充分必要条件.     

一类树关于能量的序

称一个图G的所有特征根的绝对值的和为G的能量,用E(G)表示.用Tn,d表示具有n个顶点,直径为d的树集.这里3 0d 0n-2,设T(n,d;n1,n2,…,nd-1)∈Tn,d是由路v0v1…vd的顶点vi(1 0i 0d-1)粘结ni条悬挂边得到的树,显然n=d+1+∑id=-11ni.令Tn,d={T(n,d;0,…,ni,0,…,0)|n=ni+d+1}.本文对树集Tn,d中的树依能量进行了排序.     

红黑树的高度

先证明高度是h的准红黑树至少有2「2h﹁ 2﹂2h」-2个结点.再证明有n个结点的准红黑树的高度至多是2﹂log2(n 2)」 ﹂log2(n 2lo)g-23﹂l-o1g2(n 2)」」-2.最后证明有n个结点的红黑树的高度至多是2﹂log2(n 2)」 ﹂log2(n 2lo)g-23﹂l-og12(n 2)」」-2,该式比原来的2﹂log2(n 1)」 1准确.有n个结点的红黑树的高度在﹂log2(n 1)」和2﹂log2(n 2)」 ﹂log2(n 2lo)g-23﹂l-og12(n 2)」」-2之间.此文进一步完善了红黑树的性质.     

树的m—路中心

提出了m—路中心的概念。对无权树和赋权树分别给出了O(n log n),O(n~2)及O(n log (d(T)/Wminee(T)))算法,其中Wminee(T)是赋权树的最小权数。     

(m,n)-树的一个充分必要条件

通过在(m,n)-树中引入Graham约化过程,给出了(m,n)-树的一个充分必要条件。     

关于树的第二个最大特征值

令T(n,i)表示顶点数为n,且匹配数为i的所有树的集合,研究了T(4n-1,2n-1)中哪些树的第二个最大特征值等于√1/2[n+1+√(n+1)2-8]的一个猜想.此外,还进一步得到了T(4n-1,2n-1)中树的第二个最大特征值的3个新的上界,并且确定了达到上界的所有的树.     

可微C0-半群的谱

利用可微C0-半群的若干性质给出了可微C0-半群{T(t):t≥0}的生成元A的谱与AT(t)的谱之间的关系.     

(m,n)-树的几个判定条件

通过构造(m,n)-树的(m,n)-图，给出了判断(m,n)-树的几个充分必要条件，从而进一步揭示了(m,n)-树的结构特征．     

关于一类蜘蛛树的全优美性

定义T(2m,n+1)-蜘蛛树,并给出了优美标号、全优美标号以及边对称树的概念,证明T(2m,n+1)-蜘蛛树的全优美性,以及该蜘蛛树的边对称树仍然是全优美的.     

复合毛毛虫树的优美及奇优美性

对于一棵n阶树T,如果存在一个映射f:V(T)→{0,1,2,…,n-1},对不同的顶点x,y∈V(T),有f(x)≠f(y),且边标号集合{f′(uv)|uv∈E(T)}={1,2,…,n-1},其中f′(uv)=|f(u)-f(v)|,称T为优美树,并称f为T的一个优美标号.利用优美树的定义和性质证明复合毛毛虫树的优美性和奇优美性.     

直径为4的奇优美树

对于简单图G=, 如果存在一个映射f: V→{0,1,2,...,2E|-1}满足:对任意的u,v∈V,若u≠v,则f(u)≠f(v);max{f(v)|v∈V}=2|E|-1;对任意的e1,e2∈E,若e1≠e2,则g(e1)≠g(e2),此处g(e)=|f(u)-f(v)|,e=uv;{g(e)|e∈E}={1,3,5, ...,2|E|-1},则称G为奇优美图,f 称为G的奇优美标号.提出一个猜想:每棵树都是奇优美的,文章证明了直径为4的树都是奇优美的.     

具有完美匹配且直径不大于7的强优美树

一棵具有n个顶点且有完美匹配M的树T,若有一个优美标号f使得对T的每条边uv∈M都有f(u)+f(v)=n-1,则称树T是强优美的.证明所有直径不大于7且有完美匹配的树都是强优美的,并给出了一种构造大的强优美树的方法.     

几类和扇有关图的优美性

证明下面的结论:对任意自然数n≥2,图(K_1∨(P_n∪P_(n+1)))是(n-1)-强优美图.对任意自然数n≥3,图(K_1∨P_n~((1))∪P_n~((2))))∪G是优美图;对任意自然数n≥4,图(K _1∨(P_n~((1))∪P_n~((2))∪P_n~((3)))∪H是优美图,其中k=[n/2].P_n是n个顶点的路,G_i为含有i条边的优美图.给定优美图G_(n-1)和其优美标号f,G_(k-1)和其优美标号g,设u∈G_(n-1),v∈G_(k-1)且f(u)=g(v)=0,取不同的两边xy和x′y′,点x与u合并后得到的图记为G,点x′与v合并后得到的图记为H.     

关于图C_m∪P_(n-1)~+的优美性

图Ｃｍ ∪Ｐ＋ｎ－ １ 是圈Ｃｍ 与Ｐ＋ｎ－ １ 的不交并。本文证明了当①ｍ ＝ ４ｋ,ｎ ≥ｋ ＋ ２;②ｍ ＝ ４ｋ ＋ １,４ｋ － １ ≤ｎ ≤１０ｋ－ ７;③ｍ ＝ ４ｋ＋ ２,ｎ ≥４ｋ ＋ １;④ｍ ＝ ４ｋ ＋ ３,４ｋ＋ ２≤ｎ ≤１０ｋ－ ２ 时,图Ｃｍ ∪Ｐ＋ｎ－ １ 是优美的。     

一类图的色唯一性

让W_(n,n-2)表示删去轮形图W_n中一条轮辐所得到的图.W(n,n-2,k)表示在W_(n,n-2)中由k个点u_1,u_2,…,u_t组成的独立集取代W_(n,n-2)中的2度点u,使得u_j(j=1,2,…,k)仅与u所相邻的两个点x,y相邻接而得到的。本文证明了当k=2,n≥4为偶数时,这类图是色唯一的。     

轮形图和扇形图的优美性

设L为简单无向图G的一个顶点标号,若L满足:(1)L为G的顶点集V到{0,1,…,|E|}的一个单射;(2)由L(′e)=|L(u)-L(v)|(其中e=uv)决定的边标号L′是从G的边集E到{0,1,…,|E|}的一个双射,则L称为图G的优美标号.论文研究了轮形图和扇形图的优美性,并给出它们的优美标号.     

伞状树的奇强协调性

设G=V,E是一个简单图,若存在一个映射f:V(G)→{0,1,2,…,2|E|-1}满足(1)对任意的u,v∈V,若u≠v,则f(u)≠f(v);(2)对任意的e1,e2∈E,若e1≠e2则g(e1)≠g(e2),此处g(e)=f(u)+f(v),e=uv,且{g(e)|e∈E}={1,3,5,…,2|E|-1},则称G是奇强协调图,f为G的奇强协调标号,讨论了一类树的奇强协调性.     

无K_(1,t)图的L(d,1)-T标号

给定一个连通图G=(V,E)及其一棵支撑树T,图G的一个L(d,1)-T标号即函数g:V(G)→{0,1,2,…},满足:(1)如果xy∈E(G),则|g(x)-g(y)|≥1;(2)如果dG(x,y)=2,则|g(x)-g(y)|≥1;(3)如果xy∈E(T),则|g(x)-g(y)|≥d.假设图G有一个L(d,1)-T标号函数g:g(V){0,1,2,…,k},则图G的所有L(d,1)-T标号函数中最小的整数k记为L(d,1)-T标号数λdT(G,T).本文证明了若G是无K1,t(3≤t≤n)的连通图,其最大度为Δ,|G|=n,T为G的任意支撑树,则λdT(G,T)≤tt--12Δ2+Δ+2d-2.     

图K2n\E（Fm）（n≥4,m≥2）的点可区别边染色

对简单图G(V,E),设f是从E(G)到{1,2,…,k}的映射,k为自然数,如果f满足:1)对任意的uv,uw∈E(G),v≠w,有f(uv)≠f(uw);2)对任意的u,v∈V(G),u≠v,有C(u)≠C(v).则称f为图G的k-点可区别边染色法,而最小的k被称为点可区别边色数(其中C(u)={f(uv)|uv∈E(G)}).研究了图K2n\E(Fm)(n≥4,m≥2)的点可区别边色数.