一類特殊本原不可冪定號有向圖的local基

張 波，栗 慧，邵燕靈

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

一類特殊本原不可冪定號有向圖的local基

張 波，栗 慧，邵燕靈

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

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

local基；定號有向圖；本原

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

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

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

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

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

1 相關(guān)引理

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

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

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

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

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

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

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

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

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

2 主要結(jié)果

本研究主要對一類特殊本原不可冪定號有向圖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＊是一個n階本原不可冪定號有向圖，其基礎(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é)基金資助項目（2008011009）

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

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

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