本原θ-图与本原广义θ-图的Scrambling指数  

The Scrambling Index of Primitive θ-Graph and Primitive Extended θ-Graph

作　　者：杜建伟[1,2] 邵燕灵[2] 孙晓玲[1,2] 

机构地区：[1]中北大学信息与通信工程学院,山西太原030051 [2]中北大学理学院,山西太原030051

出　　处：《中北大学学报（自然科学版）》2014年第1期1-6,共6页Journal of North University of China(Natural Science Edition)

基　　金：国家自然科学基金资助项目(11071227);山西省回国留学人员科研资助项目(2012-070);中北大学校基金资助项目(2012-121)

摘　　要：设D是本原有向图,存在正整数k,对任意一对顶点x,y,一定存在一个顶点w,使得x到y与y到x皆有k长的途径,这样的正整数中的最小者称为D的Scrambling指数.对本原θ-图与本原广义θ-图的Scrambling指数进行了研究.采用图论与组合矩阵论的方法,得到了本原θ-图与本原广义θ-图的Scrambling指数的上界,并且给出了一类Scrambling指数达到上界的本原θ-图与本原广义θ-图.Abstract： Suppose D is a primitive digraph, the Scrambling index of D is the smallest positive integer k that for every pair of vertices x and y, there exists a vertex w that there is a walk of length k from x and y to w in D. The Scrambling index of primitive θ-graph and primitive extended θ-graph was investigated. By using the method of graph theory and combinatorial matrix theory, we obtained the upper bound for the Scrambling index of primitive θ-graph and primitive extendedθ-graph; moreover, a class of primitive θ-graph and primi- tive extended θ-graph whose Scrambling index is equal to the maximum value is given.

关 键 词：本原 Θ-图 广义θ-图 SCRAMBLING指数 

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