2个特殊本原有向图的Scrambling指数与广义Scrambling指数

代爱凤，邵燕灵

（中北大学 数学系，太原 030051）

2个特殊本原有向图的Scrambling指数与广义Scrambling指数

代爱凤，邵燕灵

（中北大学 数学系，太原 030051）

考虑2个含有3个圈（其中2个圈的长度相等但不相交）的特殊本原有向图.通过分析图中每一点经过t长途径所到达的点的集合及点的个数，给出了此类图的Scrambling指数和广义Scrambling指数.

本原有向图；Scrambling指数；广义Scrambling指数

1 基本概念

设D为有向图，如果存在正整数l，使得对于D的任意顶点x、y（可以相同），在D中都存在从x到y的l长途径，则称D为本原有向图，最小的l称为D的本原指数，记为exp（D）.D是本原有向图的充分必要条件是D为强连通、且D的所有圈长的最大公因子为1［1］.

目前，对本原有向图的本原指数的研究已扩展到对本原有向图的Scrambling指数的研究，并且取得了许多成果.文献［2－3］引入了本原有向图的Scrambling指数的定义并讨论了一类含哈密顿圈且最小圈长为s的n阶本原有向图的Scrambling指数的上界.

2 主要结论

本研究考虑2个含有3个圈（其中2个圈的长度相等但不相交）的特殊本原有向图，见图1～2，得到了D1、D2的Scrambling指数和广义Scrambling指数.

图1 本原有向图D1Fig.1 Primitive digraph D1

图2 本原有向图D2Fig.2 Primitive digraph D2

［1］ BRUALDI R A，RYSER H J.Combinatorial Matrix Theory［M］.Cambridge：Cambridge University Press，1991.

［2］ AKELBEK M，KIRKLAND S.Coefficients of ergodicity and the Scrambling index［J］.Linear Algebra and Its Applications，2009，430：1111－1130.

［3］ AKELBEK M，KIRKLAND S.Primitive digraphs with the largest Scrambling index［J］.Linear Algebra and Its Applications，2009，430：1099－1110.

［4］ HUANG Y F，LIU B L.Generalized Scrambling indices of a primitive digraph［J］.Linear Algebra and Its Applications，2010，433：1798－1808.

［5］ LIU B L，HUANG Y F.The Scrambling index of primitive digraphs［J］.Computers and Mathematics with Application，2010，60：706－721.

［6］ CHEN S X，LIU B L.The Scrambling index of symmetric primitive matrices［J］.Linear Algebra and Its Applications，2010，433：1110－1126.

Scrambling indices and generalized Scrambling indices of two special primitive digraphs

DAIAi－feng，SHAOYan－ling
（Department of Mathematics，North University of China，Taiyuan 030051，China）

Two special primitive digraphs each of which contains three cycles，two cycles of which do not intersect but the lengths are equal are studied.Through analyses of the vertex set of each vertex in digraph can be reached by a walk of lengtht，the Scrambling indices and generalized Scrambling indices of such digraphs are given.

primitive digraph；Scrambling indices；generalized Scramblingindices

O157.5

A

1671－1114（2012）03－0009－04

2011－12－13

国家自然科学基金资助项目（11071227）

代爱凤（1987—），女，硕士研究生.

邵燕灵（1963—），女，教授，博士生导师，主要从事图论和组合数学方面的研究.

（责任编校 马新光）