一类特殊本原不可幂定号有向图的local基

张 波，栗 慧，邵燕灵

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

一类特殊本原不可幂定号有向图的local基

张 波，栗 慧，邵燕灵

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

对一类特殊的含有3个圈的本原不可幂定号有向图的local基进行了研究.运用“异圈对”、Frobenius集及本原指数等讨论图中是否有相应的SSSD途径对，得到了这类图的local基与基.

local基；定号有向图；本原

将有向图D（可能含有环）中的每一条弧定义一个符号1或－1所得的图称为D的定号有向图，记为S，D称为S的基础有向图.

定义1［1］如果定号有向图S中不含SSSD途径对，则称S是可幂的；否则，称S是不可幂的.

定义2［2］设D是一个有向图，如果存在正整数k，使得对于D的任意顶点vi，vj（可以相同），都有从vi到vj长为k的途径，则称D为本原有向图，最小的k称为D的本原指数，记作exp（D）.

定义4［1］设S是一个本原不可幂定号有向图，u∈V（S），若对任意t≥l，从u到任意一点v（v∈V（S））都有长为t的SSSD途径对，则称最小的正整数l为顶点u的基，记为lS（u）.

定义5［1］设S是一个本原不可幂定号有向图，若对任意顶点vi，vj（可以相同），对任意t≥l，从vi到vj都有长为t的SSSD途径对，则称最小的正整数l为定号有向图S的基，记为l（S）.

1 相关引理

引理1［4］如果S是一个本原定号有向图，那么S不可幂当且仅当S中存在一对圈C1和C2（长度分别为p1和p2），满足下面2个条件之一：

（A）p1是奇数，p2是偶数，且sgnC2＝－1；

（B）p1和p2都是奇数，且sgnC1＝－sgnC2.

为方便起见，称满足（A）或（B）的圈对C1和C2为“异圈对”.容易看到，闭圈对W1＝p2C1和W2＝p1C2有相同的长度p1p2，但符号不同，即

设x，y为本原有向图D中的有序顶点对，如果任意一个从x到y长度不小于dL（D）（x，y）的途径都由一些从x到y长为dL（D）（x，y）的途径W及若干个与W有公共点的圈组成，则称有序顶点对x，y有唯一途径性质.

设D为一个本原有向图，h为非负整数，Rh（x）表示从顶点x出发，所有经过长度为h的途径能够到达的顶点的集合.

引理3［3］设D为一个本原有向图，x，y是D中不同的2个点，且Rh（x）＝｛y｝，即从顶点x出发，长度为h的途径能够到达的顶点只有y，则

引理4［3］设S是一个本原不可幂定号有向图，x∈V（S），r（x）表示最小的正整数k，使得从x到x存在长为k的SSSD途径对，则

引理5［3］设S是一个本原不可幂定号有向图，x，y是S中不同的2个点，且Rh（x）＝｛y｝，如果从x到y所有长为h的途径的符号相同，则

2 主要结果

本研究主要对一类特殊本原不可幂定号有向图S＊的local基进行了研究，其基础图为D＊（见图1），其中，m＋1与n－2互素，m≥2，且n＞m＋3.

图1 基础图D＊Figure 1 Basic graph D＊

定理 设S＊是一个n阶本原不可幂定号有向图，其基础图为D＊，则有

［1］ Gao Y B，Shao Y L，Shen J.Bounds on the local bases of primitive nonpowerful nearly reducible sign patterns［J］.Linear and Multilinear Algebra，2009，57（2）：205－215.

［2］ Li Q，Liu B L.Bounds on thekth multi－gbase index of nearly reducible sign pattern matrices［J］.Discrete Mathematics，2008，308：4846－4860.

［3］ Ma H P.Bounds on the local bases of primitive，non－powerful，minimally strong signed digraphs［J］.Linear Algebra and its Applications，2009，430：718－731.

［4］ You L H，Shao J Y，Shan H Y.Bounds on the bases of irreducible generalized sign pattern matrices［J］.Linear Algebra and Its Applications，2007，427：285－300.

［5］ Shao J Y.On the exponent of a primitive digraph［J］.Linear Algebra and Its Applications，1985，64：21－31.

［6］ Dulmage A L，Mendelsohn N S.Gaps in the exponent set of primitive matrices［J］.Illinois J Math，1964，8：642－656.

Local bases of a special class of primitive non－powerful signed digraphs

ZHANGBo，LIHui，SHAOYanling
（Department of Mathematics，North University of China，Taiyuan 030051，China）

The local bases is studied for a special class of primitive non－powerful signed digraphs with three cycles.The knowledge about“distinguished cycle pair”，Frobenius set and exponent are used to discuss whether there is a pair of related SSSD walks in digraphs，and the local bases and bases are obtained for the class of digraphs.

local bases；signed digraphs；primitive

O157.5

A

1671－1114（2011）02－0016－04

2010－05－07

山西省自然科学基金资助项目（2008011009）

张 波（1983—），男，硕士研究生.

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

（责任编校 马新光）