一個恰含三個圈的本原不可冪定號有向圖的基

趙 晶，高玉斌

（中北大學 理學院，山西 太原 030051）

一個恰含三個圈的本原不可冪定號有向圖的基

趙 晶，高玉斌

（中北大學 理學院，山西 太原 030051）

為了進一步了解本原不可冪定號有向圖的基的特點及有關性質，對一個特殊的本原不可冪定號有向圖的基進行了研究．通過分析這個圖的特點，運用反證法并結合圖中的本原指數、點指數、基指數、Frobenius集、可冪與不可冪及“異圈對”等定義和性質得出基的具體值．

本原；定號有向圖；不可冪；基

0 引言

一個實數a的符號sgna，根據a＞ 0，a＜ 0或a= 0，被定義為1，?1或0．將一個有向圖D（允許含有環但不能有重弧）中的每一條弧賦予符號1或?1所得的圖稱為D的定號有向圖，記為S，稱D為S的基礎有向圖．定號有向圖S中的一條途徑W是一個有關弧的序列e1，e2，…，ek，使得ei的終點與ei+1的起點相同，其中i=1， …，k?1，所含弧的條數k被稱為途徑W的長度，記為l(W).途徑W的符號定義為W中所有弧的符號的乘積（重復出現的弧的符號重復計算），即記為sgnW[2]．

1 基本概念與引理

設D是一個有向圖，如果存在正整數k，使得對于D中的任意一對頂點vi和vj（可以相同），在D中都存在從vi到vj長為k的途徑，則稱D為本原有向圖．上述最小的k被稱為D的本原指數，記為exp(D).設D是一個本原有向圖，vi∈D，如果存在正整數p，對任意的t≥p，從頂點vi到D中的任一點都有長為t的途徑，那么上述最小的正整數p被稱為頂點vi的點指數，記為expD(vi)[3]．設S是一個本原不可冪定號有向圖，若對任意頂點vi和vj（可以相同），并且對任意t≥l，從vi到vj都有長為t的SSSD途徑，則上述最小的正整數l被稱為S的基，記為l(S).W1和W2是S中的兩條途徑，若它們的起點、終點、長度相同，但符號不同，則稱W1和W2為SSSD途徑對[4]．若S中不包含SSSD途徑對，則稱S為可冪的，否則稱S為不可冪的[5]．

引理1[6―7]如果S是一個本原定號有向圖，那么S不可冪的充分必要條件是S中存在一對長度分別為p1和p2的不同的圈C1和C2，且滿足下面兩個條件之一：

(a)p1是奇數，p2是偶數，且 sgnC2= ?1；

(b)p1和p2都是奇數，且 sgnC1=? sgnC2.

為方便起見，滿足條件(a)或(b)的圈對C1和C2稱為“異圈對”．容易看出，此時，閉途徑對W1=p2C1和W2=p1C2有相同的長度，但有不同的符號：

設R={l1，…，lk}為本原有向圖D的圈長的集合，且g.c.d(l1，…，lk)=1．對于D中的每個頂點x和頂點y，設d(x，y)為從 到y的距離，dR(x，y)表示從 到y接觸R中每一長度的圈的最小距離．用

引理 2[7]設S是一個n階本原不可冪定號有向圖，其基礎圖為D．d(S)表示S的直徑，W1和W2為從點u到v的長度為r的SSSD途徑對，則有

有關定號有向圖基的研究，目前取得了一些結果．文獻[1]介紹了含有環的本原不可冪定號對稱有向圖的基；文獻[3]介紹了可約符號模式矩陣周期與基；文獻[7]給出了幾乎可約符號模式矩陣基的界．

本文主要研究一個本原不可冪定號有向圖S，其基礎圖D如圖1．容易看出，圖1所示的基礎圖D是由兩個圈長為n?5和一個圈長為n?3的3個不同的圈組成的．

圖0 定號有向圖S的基礎圖D

2 主要結論

定理1設S是一個n階（n≥10）本原不可冪定號有向圖，基礎圖D如圖1所示，則

定理1證畢．

[1] Gao Yubin，Huang Yihua，Shao Yanling．Bases of primitive non-powerful singed symmetric digraphs with loops[J]．Ars Combinatoria，2009，90：383―388．

[2] Li Z Hall F，Stuart L．Irreducible powerful ray pattern matrices[J]．Linear Algebra Appl，2002，342：47―58．

[3] Liu Bolian．The period and base of a reducible sign pattern matrix[J]．Discrete Mathematics，2007，307：3031―3039．

[4] Gao Yubin，Shao Yanling．Generalized exponents of primitive two-colored digraphs[J]．Linear Algebra and its Applications，2009，430：1550―1565．

[5] Lundgren J R ，Maybee J S．Some properties of a class of recursively defined digraphs[J]．System Sci.，1991，16(1)：29―36．

[6] Wang Longqin，Miao Zhengke，Yan Chao．Local bases of primitive non-powerful signed digraphs[J]．Discrete Mathematics，2009，309：748―754．

[7] Liu Bolian，You Lihua．Bounds on the base of primitive nearly reducible sign pattern matrices[J]．Linear Algebra and its Applications，2006，418：863–881．

Bases of a Primitive Non-powerful Signed Digraph that Just Has Three Cycles

ZHAO Jing, GAO Yu-bin
(North Central University, Taiyuan Shanxi 030051, China)

In order to further understand characteristics and properties of the bases of primitive non-powerful signed digraph, a primitive non-powerful signed digraph with three cycles are studied in this work. By analyzing the features of the digraph, using apagoge and knowledge about primitive exponents, point exponents, bases, Frobenius set, powerful, non-powerful and“distinguished cycle pair”, then the true values of bases are got.

primitive; signed digraph; non-powerful; bases

O157.5

A

1006-5261(2011)05-0001-03

2011-06-14

山西省自然科學基金資助項目（2008011009）

趙晶（1985―），女，山西太原人，碩士研究生；高玉斌（1962―），男，教授，博士，博士生導師．

〔責任編輯 張繼金〕