一类双色有向图的本原指数的上界

李 茜，罗美金

（1.山西运城农业职业技术学院 基础部，山西 运城 044000；2.河池学院 数学与统计学院，广西 宜州 546300）

一类双色有向图的本原指数的上界

李 茜1，罗美金2*

（1.山西运城农业职业技术学院 基础部，山西 运城 044000；2.河池学院 数学与统计学院，广西 宜州 546300）

研究一类双色有向图，其基础有向图仅包含两个圈，分别是n-圈与（3n-1）-圈，并给出了这个双色有向图的本原条件、本原指数上界，以及对达到上界的极图进行了刻画.

双色有向图；本原指数；极图

一个双色有向图是指其弧被着色为红色、蓝色的有向图.若对D的任一对顶点（i，j），都有从i到j的途径，则称双色有向图D是强连通的.对于双色有向图D的一条途径w，用r（w），b（w）分别表示w的红弧、蓝弧的个数，则w分解为向量（r（w），b（w））或（r（w），b（w））T.若w的分解为（h，k），则称w为一条（h，k）-途径.

双色有向图D是本原的，若存在非负整数h和k且h+k>0，使得对于D中的每对顶点（i，j），都有从i到j的（h，k）-途径.并将h+k的最小值称为双色有向图D的本原指数，记为exp（D）.

设C={r1，r2，…，rl}是D的圈的集合，M为2×l矩阵，其第i列是ri的分解，则称M为D的圈矩阵.将M的content（记为content（M））定义为0，若M的秩小于2，否则，定义为M的所有非零二阶主子式的最大公因子.

目前，关于双色有向图的本原指数的研究已经取得了一些成果，参见文献[1-8].本文研究一类双圈双色有向图D，其基础有向图见图1.

图1 基础有向图Fig.1Uncolored digraph D

1 本原条件

引理1[1]一个至少包含一条红弧和一条蓝弧的双色有向图D是本原的，当且仅当D是强连通的，且content（M）=1.

定理1 双色有向图D是本原的，当且仅当

a（3n-1）-bn=±1，且

（1）当a（3n-1）-bn=1时，a=n-1，b=3n-4.

（2）当a（3n-1）-bn=-1时，a=1，b=3.

证明 显然D是强连通的，det（M）=a（3n-1）-bn.由引理1，D是本原的当且仅当det（M）=±1，即a（3n-1）-bn=±1.容易验证，当a（3n-1）-bn=1时，a=n-1，b= 3n-4；当a（3n-1）-bn=-1时，a=1，b=3.证毕.

2 本原指数的上界

定理2 若双色有向图D是本原的，且a（3n-1）-bn=1，则exp（D）≤24n2-31n+4.

证明 由定理1，D的圈矩阵为

对于D的每对顶点（i，j），用Pij表示从i到j的最短路，s=r（Pij），t=b（Pij）.

只需证明对于D的每对顶点（i，j），都有一条（24n2-55n+31，24n-27）-途径.取

因此，从顶点i出发，沿Pij到顶点j，转n-圈ρ1次，转（3n-1）-圈ρ2次，其途径可分解为

显然，s≤4n-5，t≤4，且ρ1≥0，ρ2≥0.当s=4n-5时，t≥0.当t=4时，s≥0.此时必包含公共顶点n.

所以exp（D）≤24n2-55n+31+24n-27=24n2-31n+ 4.证毕.

定理3 若双色有向图D本原，且a（3n-1）-bn= -1，则exp（D）≤24n2-31n+4.

证明 类似于定理2可证.

3 指数上界的极图刻画

定理4 若双色有向图D是本原的，且a（3n-1）-bn=1，则exp（D）=24n2-31n+4，当且仅当D中存在4n-5长的连续红路.

证明 充分性：由定理2，只需证明exp（D）≥24n2-31n+4.

所以，v≥4n-4.

则

结合定理2，可得exp（D）=24n2-31n+4.

必要性：反证法.假设D中不存在4n-5长的连续红路，因为D是本原的，且a（3n-1）-bn=1，所以只需证明exp（D）<24n2-31n+4.

对于D的每对顶点（i，j），用Pij表示从i到j的最短路，s=r（Pij），t=b（Pij）.

只需证明对于D的每对顶点（i，j）都有一条（24n2-61n+38，24n-33）-途径.取

ρ1=12n-18-3s+（3n-4）t，ρ2=4n-5-（n-1）t+s，因此，从顶点i出发，沿Pij到顶点j，转n-圈ρ1次，转（3n-1）-圈ρ2次的途径可分解为

显然，s≤4n-5，t≤4.

（1）当t=0时，0≤s≤4n-6.且ρ1≥0，ρ2>0.

（2）当t=1时，0≤s≤4n-5.且ρ1>0，ρ2>0.

（3）当t=2时，0≤s≤4n-5.且ρ1>0，ρ2>0.

（4）当t=3时，0≤s≤4n-6.且ρ1>0，ρ2>0.

（5）当t=4时，1≤s≤4n-7.且ρ1>0，ρ2≥0.

所以，

证毕.

定理5 若双色有向图D本原，且a（3n-1）-bn= -1，则exp（D）=24n2-31n+4，当且仅当D中存在4n-5长的连续蓝路.

证明 类似于定理4可证.

[1]Shader B L,Suwilo S.Exponents of nonnegative matrix pairs [J].Linear Algebra and Its Applications,2003,363:275-293.

[2]Shao Yanling,Gao Yubin,Sun Liang.Exponents of a class of two-colored digraphs[J].Linear and Multilinear Algrbra, 2005,53(3):175-188.

[3]Gao Yubin,Shao Yanling.Exponents of two-colored di⁃graphs with two cycles[J].Linear Algebra and Its Applica⁃tions,2005,407:263-276.

[4]Gao Yubin,Shao Yanling.Generalized exponents of primi⁃tive two-colored digraphs[J].Linear Algebra and Its Appli⁃cations,2008,430(5):1550-1565.

[5]Shao Yanling,Gao Yubin,Sun Liang.On the exponents of two-colored digraphs with two cycles[J].Linear and Multi⁃linear Algebra,2009,57(2):185-199.

[6]罗美金.一类双色有向图的本原指数集[J].数学的实践与认识,2012,42(24):253-258.

[7]罗美金.一类双色有向图的本原指数上界[J].数学的实践与认识,2013,43(23):142-150.

[8]罗美金.一类恰含一个公共点的双色有向图的本原指数集[J].暨南大学学报:自然科学与医学版,2013,34(5):483-488.

责任编辑：毕和平

Upper Bound on Primitive Exponent of a Class of Two-colored Digraphs

LI Xi1，LUO Meijin2＊
（1.Department of Basic Education，Yuncheng Vocational College of Agriculture，Yuncheng044000，China；2.School of Mathematics and Statistics，Hechi University，Yizhou546300，China）

A class of two-colored digraphs whose uncolored digraph consists of onen-cycle and one（3n-1）-cycle.Some primitive conditions,an upper bound on the exponent,and the characterizations of the extremal two-colored digraphs.

two-colored digraph；primitive exponent；extremal digraph

O 157.5

：A

：1674-4942（2015）01-0020-02

2014-10-29

广西自治区高等学校科研项目（YB2014335）

*通讯作者