一些特殊树的对偶带宽(英文)  

Dual Bandwidth of Some Special Trees

作　　者：要卫丽[1] 鲁晓旭[1] 周菊[1] 

机构地区：[1]郑州大学数学系,郑州450052

出　　处：《郑州大学学报（理学版）》2003年第3期16-19,共4页Journal of Zhengzhou University:Natural Science Edition

摘　　要：图G的对偶带宽是指图G中相邻两点最小标号差的最大值 .确定了一些特殊树的对偶带宽 ,主要结果如下 :(1)如果树T有n个顶点 ,并且其最大度Δ(T)不小于「n2 ,那么树T的对偶带宽等于n -Δ(T)的充要条件为T是双层星且其内星的中心为最大度顶点 ;(2 )完全二叉树T2 ,k的对偶带宽等于 2 k- 1;(3)等高单毛虫树Pm ,n的对偶带宽为 mn2 」 .The dual bandwidth of a graph G,denoted by (G),is the maximum value of the minimum labelling variance of any two adjacent vertices in G.The dual bandwidth is determined for some special trees.The main results are as follows:(1)For a tree T with n vertices and with Δ(T)≥「n2?,(T)=n-Δ(T) if and only if T is two-layer star such that the center of inner star is of degree Δ(T).(2)The dual bandwidth of uniform binary tree T 2,k is (T 2,k)=2 k-1.(3)The dual bandwidth of caterpillar P m,n is (P m,n)=? mn2」.

关 键 词：图论 对偶带宽 最小标号差 最大度顶点 树 

分 类 号：O157.5[理学—数学]