具有最大基指数的本原不可幂带号简单图

《具有最大基指数的本原不可幂带号简单图》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第37卷第6期应用数学学报Vo1．37No．62014年11月ACTAMATHEMATICAEAPPLICATAESINICANov．，2014具有最大基指数的本原不可幂带号简单图陈佘喜(湖南科技大学数学与计算科学学院，湘潭411201)(E-mail：sxchen@hnust．edu．CYI)刘建勋(湖南省普通高校知识处理与网络化制造重点实验室，湘潭411201)马钰(湖南科技大学数学与计算科学学院，湘潭411201)摘要一个本原不可幂带号有向图S的基指数f(s)是这样的最小正整数l，使得在S中，从任意一点“到任意一点都

2、有一对长为l的SSSD途径．本文给出了本原不可幂带号简单图的基指数的最大值，并完全刻划了具有最大基指数的本原不可幂带号简单图．关键词本原有向图；基指数；不可幂MR(2000)主题分类05C20；05C50；15A48中图分类O157．51引言一个带号有向图s是指将有向图D(允许有环但不允许有重复弧)的每条弧都赋以符号1或者一1所得的图．此时，称D是的基础图．s中一个非空的点弧交错序列W：V0，e1，V一，e，V称为s的一条途径，如果仇一1，Vi分别是弧ei的始点与终点，i=1，2，⋯，．此时，称k为途径的长，记作1『，并定

3、义途径的符号为sgnW=1-Isgn(ei)，其中sgn(ei)表示弧ei的符号．特别地，若lWl=0，则规定t=1sgnW=1．若途径中的顶点Vo，⋯，Vk一1，Vk均不同，则称之为路．若Vk=V0，则称本文2014年3月3日收到．2014年l0月13日收到修改稿．国家自然科学基金(61272109，61272063)和湖南省科技计划(2012FJ4330)资助项目998应用数学学报37卷途径是闭的．闭途径中除Vk=Vo外，所有点”o⋯．，一均不同，则称为圈．带号有向图s是本原的，如果其基础图D是本原的，即J[)是强连通

4、的且所有圈长的最大公因数是1[1】．一个有向图D称为对称有向图，若D中任意点i到任意点．有弧当且仅当J到i有弧．显然，一个对称有向图可以等同于一个无向图．熟知，一个无向图是本原的，当且仅当其连通且至少包含一个奇圈_2]．对称带号有向图是指其基础图是对称有向图，且其任意一对对称弧(i，J)与(J，i)所带有的符号相同．一个对称带号有向图可视为一个带号的无向图，其每边都带有符号1或者一1．带号有向图s中两条同始同终同长不同号的途径与W2称为s的一对SSSD途径．如果s不含任何SSSD途径对，则称s是可幂的．否则，称s是不可幂的

5、．如果S是本原不可幂带号有向图，那么S中任意两顶点间都存在SSSD途径对_3】．设s是本原不可幂带号有向图．S的基指数f(s)是这样的最小正整数f，使得在s中，从任意一点到任意一点V都有长为2的SSSD途径对[3】_从顶点到顶点V的基指数是这样的最小正整数ls(u，)，使得对任意的正整数tls(u，V)，在s中存在从点到点u的长为t的SSSD途径对_4J．迄今，一批学者在不可幂带号有向图(符号矩阵)的基指数的研究中取得了许多好结果．尤利华、邵嘉裕和单海英[。]研究了不可幂符号矩阵的幂序列性质，给出了不可幂符号矩阵的基指数的

6、最大值．程波和柳柏濂[】确定了零对称本原不可幂符号矩阵的基指数的最大值和基指数集．高玉斌、黄以华和邵燕灵【】确定了含环的本原不可幂带号对称有向图的基指数的最大值与基指数集．于广龙、苗正科和束金龙[。】确定了恰含d个非零对角元的本原不可幂符号矩阵的基指数的最大值和基指数集．基指数在非记忆通讯网络等领域有明确的应用背景．例如，带号有向图(符号矩阵)可用来描述有反向器的非记忆信息传递系统，基指数就是引起系统信息传递混乱的最小时间[7】_下面的定理是关于本原不可幂带号有向图的重要刻划．定理1．1【0]设s是一个本原带号有向图．那么

7、，s是不可幂的，当且仅当s中存在一对长分别为P与P的圈c与，满足以下条件之一：(B1)Pi是奇数，P是偶数，且sgnCj=一1，其中{，l7)={1，2)．(B2)p1与p2都是奇数且sgnC1=-sgnC2．为了表述方便，称满足(B)或(B2)的圈对c与为一对特异圈．定理1．2[】设s是本原不可幂带号有向图．那么2(s)=max{zs(u，V)l札，V∈(s))定理1．3[]设S是最小奇圈长为r的佗阶本原不可幂带号无向图，那么zcs{2n-1，一，：：c．2本文考虑本原不可幂带号简单图，即至少含有一对特异(无向)圈的连通

8、简单图．6期陈佘喜，刘建勋，马钰：具有最大基指数的本原不可幂带号简单图999以下用PNSG(n)表示所有的札阶本原不可幂简单图的集合．对任意的S∈PNSG(n)，s中的任意带号奇圈的长r不小于3，因此，由式(1．2)的第二部分，z(s)2n一4．再由s的任意性，m&x{f(s)lS∈PNSG(n)}2n