一类恰含两个圈的本原不可幂定号有向图的广义基

霍丽芳,高玉斌

(1.中北大学理学院,山西太原030051;2.河北建筑工程学院数理系,河北张家口075024)

一类恰含两个圈的本原不可幂定号有向图的广义基

霍丽芳1,2,高玉斌1

(1.中北大学理学院,山西太原030051;2.河北建筑工程学院数理系,河北张家口075024)

研究了一类恰含两个圈的本原不可幂定号有向图,通过分析图形特点,综合利用 SSSD途径对和Frobenius指数的特性推导出这类图的广义基.

本原图;定号有向图;SSSD途径对;广义本原指数;广义基

1 基本概念

定义1.1 设D是一个有向图 (允许有环但不能有重弧),如果存在一个正整数 k,使得 D中任意两个顶点vi和vj(可以相同)都有长为 k的途径,则称 D是本原的,最小的 k就是D的本原指数,记作exp (D).

定义1.2 设 D是一个有向图,对于 vi∈D,存在正整数 m,从 vi到D中任意一点都有长为t≥m的途径,满足条件的最小的m就是vi的点指数,记作expD(vi).

为方便,令V(D)= {v1,v2,…,vn},可将 D中顶点适当调序使得expD(v1) ≤expD(v2) ≤…≤expD(vn),称expD(vk)为D的第k个广义本原指数,记为expD(k).

定义1.3 设D是有向图,将 D中的每条弧被标记1为-1,则称为定号有向图,记为S.定号有向图S中的一条途径W是由一系列的弧e1,e2,…,ek组成的,并且ei的终点与ei+1的始点相同 (i=1,2,…,k-1).途径中弧的条数就是途径W的长度,记为 l(W).途径W的符号被定义为∏ki=1sgn {ei},记为sgn W.

定义1.4 在定号有向图中的两条途径W1和W2,如果它们有相同的起始点,相同的长度,不同的符号,则称它们为SSSD途径对.

定义1.5 设S是定号有向图,如果S中不含SSSD途径对,则S是可幂的;否则,是不可幂的.

定义1.6 设 S是一个本原不可幂定号有向图,使得对任意t≥l及S中任意两个顶点vi和j(可以相同),从 vi到vj都有长为t的SSSD途径对,则称最小的 l是定号有向图S的基,记作 l(S).

定义1.7 设S是一个本原不可幂定号有向图,对于 vi∈S,存在正整数m,从vi到S中任意一点都有长为t≥m的SSSD途径对,满足条件的最小m的就是vi的点基,记作lS(vi).

为方便,令V(S)= {v1,v2,…,vn},则 S中顶点适当调序后可得lS(v1)≤lS(v2) ≤…≤lS(vn),称lS(vk)为S的第k个广义基,记作lS(k).

2 相关知识与理论

命题2.1[1]如果S是一个本原定号有向图,那么S是不可幂的充分必要条件是S中包含的一对长度分别为 p1和 p2的圈和 C1和 C2满足下面两个条件之一:

(A)p1是奇数,p2是偶数,并且有sgnC2=-1.

(B) p1和 p2都是奇数,并且有sgnC1=-sgnC2.

为方便起见,满足(A)或(B)的圈对 C1和 C2成为“异圈对”.容易看到若 C1和 C2是长分别为 p1和p2的异圈对,则闭途径对W1=p2C1和W2=p1C2有相同的长度 p1p2,但有不同的符号:

设a1,…,ak是非负整数,定义 Frobenius集为:S (a1,…,ak) = {r1a1+…+rkak|r1,…,rk是非负整数}.根据Schur引理,如果gcd(a1,…,ak) =1,那么 S(a1,…,ak)包含所有足够大的非负整数.在这种情况下,定义 Frobenius数φ (a1,…,ak)为对于所有整数 m≥φ,使得 m∈S(a1,…,ak)成立的最小整数φ.

根据上述定义,有φ (a1,…,ak) -1不属于 S(a1,…,ak).另外,如果 a,b是互素的非负整数,那么

引理2.1[2]设D是一个本原有向图,L是圈长集合.设 {p,q} ⊆L,gcd(p,q) =1,且 p＜q.若D中包含长为p,q的两个交叉的圈,则当1≤k≤n时有expD(k) ≤p(q-2) +n-q+k.

引理2.2[3]设 S是本原不可幂定号有向图,且 u∈V (S),若从 u→u有一对长为r的SSSD的途径对,则 lS(u)≤expS(u)+r.

引理2.3[4]设 S是n阶本原不可幂定号有向图,x,y是S中不同的两个点且Rt(x) = {y}(其中Rt(x)表示从 x出发经过t长途径到达顶点的集合).若从 x→y的所有t长途径都有相同的符号,则 ls(x) =lS(y) +t.

特殊地,若R1(k+1) = {k},则 lS(k+1) =lS(k)+1 (3)本文主要是对一类本原不可幂定号有向图S进行研究,通过研究我们得出如下主要结果.

3 主要结论

定理:设S是一个本原不可幂定号有向图,D是其基础图,如图1所示,则

图1 有向图 D

[1] You LH,Shao JY,Shan HY.Boundson the basesof irreducible generalized sign pattern matrices[J].Linear A lgebra App l,427(2007)：285-300

[2] Shen J,Neufeld S.Local exponents of p rimitive digraphs[J].Linear A lgebra App l.1998,268：117-129

[3] Gao YB,Shao YL,Shen J.Bounds on the local bases of p rimitive non-powerful nearly reducible sign patterns[J].Linear M ultil A lgebra,2009,57(2)：205-215

[4] Ma HP.Boundson the local basesof p rimitive,non-powerful,minimally strong signed digraphs[J].Linear A lgebra App l,2009,430：718-731

Generalized Bases of a Class of Prim itive Non-powerful Signed Nearly Reducible Digraphs with Two Cycles

HUO Li-fang1,2,GAO Yu-bin1
(1.College of Science,No rth University of China,Taiyuan 030051,Shanxi,China;2.Department of Mathematics and Physics,Hebei Institute of A rchitecture and Civil Engineering,Zhangjiakou 075024,Hebei,China)

The generalized bases of a class of prim itive non-pow erful nearly reducible signed digraphs w ith two cycles are discussed.With the analysisof this digragh and the characteristicsof SSSD walks and Frobenius,the generalized bases of this class digraphs are concluded.

p rimitive digraph;signed digraph;SSSD walks;generalized exponent;generalized base

O 157.5

A

1673-1492(2010)01-0006-03

来稿日期：2009-11-04

山西省自然科学基金资助项目 (2007011017,2008011009)

霍丽芳(1979-),女,河北万全人,河北建筑工程学院讲师,硕士研究生.

刘守义]