摘要
设 T(n,d)表示丛体恰含 d(d≥0)个环点的 n 阶无圈图构成的集合.文中证明了 T(n,d)的传递指数集 t_(n,d)为:t_(n,0)={1}∪{m|2≤m≤n—1且 m 为偶数}t_(n,1)={1}∪{2,4,…,2n—2}t_(n,d){1,2,…,n—1}∪({n,n+1,…,2(n—d)}∩{2i|i—1,2,…,n—d})(d≥2)进一步还刻划了传递指数分别达到上界 n—1,n—2,2n—2,及 max{n—1,2(n—d)}的极图的特征.
Let T(n,d)denote the set of all acyclic graphs of order n which have exactly d loops.In this paper,we have proved that the set t_(k,d)of the transitive index of T(n,d)is: t_(R,0)={1}∪{m|2≤m≤n-1,m is even} t_(R,1)={1}∪{2,4,…,2n-2} t_(R,d)={1,2,…,n-1}∪(n,n+1,…,2(n-d)}∩{2i|i=1,2…,n-d})(d≥2) Moreover,we have also obtained a characterization of the extremal graph whose transitive index is equal to n-1,n-2,2n-2 and max{n-1,2(n-d)}respectively.
出处
《西安电子科技大学学报》
EI
CAS
CSCD
北大核心
1996年第S1期177-180,共4页
Journal of Xidian University
关键词
无圈图
传递指数
本原指数
acyclic graph
transitive index
exponent
