局部几乎正则多部竞赛图中的外路  

Two Outpaths in Locally Almost Regular Multipartite Tournaments

作　　者：何志红[1] 周学勤[1] 王晓英[2] 

机构地区：[1]烟台大学数学与信息科学学院,山东烟台264005 [2]赤峰学院数学院,内蒙古赤峰024000

出　　处：《烟台大学学报（自然科学与工程版）》2009年第4期251-254,281,共5页Journal of Yantai University(Natural Science and Engineering Edition)

摘　　要：有向图中一点u(一条弧uv)的一条外路指的是从u(uv)开始的一条有向路,如果u控制路的终点当且仅当终点也控制u.一个n-部竞赛图是n-部完全图的一个定向.令V1,V2,…,Vn是n-部有向图D的部集.如果D中存在2条外路P和P使'得对于每一个i∈{1,2,…,n}都有Vi∩(V(P)∪V(P)')≠Ф,则称P和P是'D的一对分量共轭外路.定义D的局部非正则度为il(D)=max|d+(x)-d-(x)|,x∈V(D),其中d+(x)和d-(x)分别表示点x的出度和入度.如果il(D)≤1,则D是局部几乎正则的.本文证明了每一个部集具有相等的基数的局部几乎正则多部竞赛图都包含2条长至少为2的分量共轭外路.An outpath of a vertex u（an arc uv,respectively） in a digraph is a directed path starting at u（u v,respectively） such that u dominates the endvertex of the path only if the endvertex also dominates u.A n-partite tournament is an orientation of a complete n-partite graph.Let V1,V2,…,Vn be the partite sets of D.If there exist two vertex disjoint outpaths P and P in D such that Vi∩（V（P）∪V（P ））≠Ф for all i∈{1,2,…,n},P and P are a pair of componentwise complementary outpaths of D.The local irregularity is defined by it （D） = maxld＋ （x） - d - （x）｜ , x∈ V（D） over all vertices u of D, where d - （x） and d - （x） are the outdegree and indegree of u, respectively. If it（D） ≤1, D is locally almost regular. It is shown that if D whose all partite sets have the same cardinality is a locally almost regular multipartite tournament, D contains a pair of componentwise complementary outpaths.

关 键 词：分量共轭外路 局部几乎正则 多部竞赛图 

分 类 号：O157.5[理学—数学]