張 波，栗 慧，邵燕靈

（中北大學(xué) 數(shù)學(xué)系，太原 030051）

一類特殊本原不可冪定號(hào)有向圖的local基

張 波，栗 慧，邵燕靈

（中北大學(xué) 數(shù)學(xué)系，太原 030051）

對(duì)一類特殊的含有3個(gè)圈的本原不可冪定號(hào)有向圖的local基進(jìn)行了研究.運(yùn)用“異圈對(duì)”、Frobenius集及本原指數(shù)等討論圖中是否有相應(yīng)的SSSD途徑對(duì)，得到了這類圖的local基與基.

local基；定號(hào)有向圖；本原

將有向圖D（可能含有環(huán)）中的每一條弧定義一個(gè)符號(hào)1或－1所得的圖稱為D的定號(hào)有向圖，記為S，D稱為S的基礎(chǔ)有向圖.

定義1［1］如果定號(hào)有向圖S中不含SSSD途徑對(duì)，則稱S是可冪的；否則，稱S是不可冪的.

定義2［2］設(shè)D是一個(gè)有向圖，如果存在正整數(shù)k，使得對(duì)于D的任意頂點(diǎn)vi，vj（可以相同），都有從vi到vj長(zhǎng)為k的途徑，則稱D為本原有向圖，最小的k稱為D的本原指數(shù)，記作exp（D）.

定義4［1］設(shè)S是一個(gè)本原不可冪定號(hào)有向圖，u∈V（S），若對(duì)任意t≥l，從u到任意一點(diǎn)v（v∈V（S））都有長(zhǎng)為t的SSSD途徑對(duì)，則稱最小的正整數(shù)l為頂點(diǎn)u的基，記為lS（u）.

定義5［1］設(shè)S是一個(gè)本原不可冪定號(hào)有向圖，若對(duì)任意頂點(diǎn)vi，vj（可以相同），對(duì)任意t≥l，從vi到vj都有長(zhǎng)為t的SSSD途徑對(duì)，則稱最小的正整數(shù)l為定號(hào)有向圖S的基，記為l（S）.

1 相關(guān)引理

引理1［4］如果S是一個(gè)本原定號(hào)有向圖，那么S不可冪當(dāng)且僅當(dāng)S中存在一對(duì)圈C1和C2（長(zhǎng)度分別為p1和p2），滿足下面2個(gè)條件之一：

（A）p1是奇數(shù)，p2是偶數(shù)，且sgnC2＝－1；

（B）p1和p2都是奇數(shù)，且sgnC1＝－sgnC2.

為方便起見，稱滿足（A）或（B）的圈對(duì)C1和C2為“異圈對(duì)”.容易看到，閉圈對(duì)W1＝p2C1和W2＝p1C2有相同的長(zhǎng)度p1p2，但符號(hào)不同，即

設(shè)x，y為本原有向圖D中的有序頂點(diǎn)對(duì)，如果任意一個(gè)從x到y(tǒng)長(zhǎng)度不小于dL（D）（x，y）的途徑都由一些從x到y(tǒng)長(zhǎng)為dL（D）（x，y）的途徑W及若干個(gè)與W有公共點(diǎn)的圈組成，則稱有序頂點(diǎn)對(duì)x，y有唯一途徑性質(zhì).

設(shè)D為一個(gè)本原有向圖，h為非負(fù)整數(shù)，Rh（x）表示從頂點(diǎn)x出發(fā)，所有經(jīng)過長(zhǎng)度為h的途徑能夠到達(dá)的頂點(diǎn)的集合.

引理3［3］設(shè)D為一個(gè)本原有向圖，x，y是D中不同的2個(gè)點(diǎn)，且Rh（x）＝｛y｝，即從頂點(diǎn)x出發(fā)，長(zhǎng)度為h的途徑能夠到達(dá)的頂點(diǎn)只有y，則

引理4［3］設(shè)S是一個(gè)本原不可冪定號(hào)有向圖，x∈V（S），r（x）表示最小的正整數(shù)k，使得從x到x存在長(zhǎng)為k的SSSD途徑對(duì)，則

引理5［3］設(shè)S是一個(gè)本原不可冪定號(hào)有向圖，x，y是S中不同的2個(gè)點(diǎn)，且Rh（x）＝｛y｝，如果從x到y(tǒng)所有長(zhǎng)為h的途徑的符號(hào)相同，則

2 主要結(jié)果

本研究主要對(duì)一類特殊本原不可冪定號(hào)有向圖S＊的local基進(jìn)行了研究，其基礎(chǔ)圖為D＊（見圖1），其中，m＋1與n－2互素，m≥2，且n＞m＋3.

圖1 基礎(chǔ)圖D＊Figure 1 Basic graph D＊

定理 設(shè)S＊是一個(gè)n階本原不可冪定號(hào)有向圖，其基礎(chǔ)圖為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”，F(xiàn)robenius 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

山西省自然科學(xué)基金資助項(xiàng)目（2008011009）

張 波（1983—），男，碩士研究生.

邵燕靈（1963—），女，教授，博士生導(dǎo)師，主要從事組合數(shù)學(xué)方面的研究.

（責(zé)任編校 馬新光）