二部竞赛图中的最长圈问题  

Longest Cycles in Special Tournaments

作　　者：唐静[1] 赵美利[1] 

机构地区：[1]滁州城市职业学院,安徽滁州233100

出　　处：《甘肃联合大学学报（自然科学版）》2011年第4期28-30,共3页Journal of Gansu Lianhe University :Natural Sciences

摘　　要：若有向图T满足条件：uv A（T）且存在一点w使得uw∈A（T）,wv∈A（T）则d-（u）＋d＋（v）≥n,称图T满足G（n）条件.在本文中,我们讨论了如果T（p,q）二部竞赛图满足G（n）条件且强连通,则T（p,q）包含一条长至少为2 min{n＋1,p,q}的圈,除非n为偶数且T（p,q）同构于一类图族B（k1,k2,k3,n/2）,ki≥n/2,i=1,2,3,及特殊竞赛图的最长圈问题.A digraph T is said to satisfy the condition G（n） if d-（u）＋d＋（v）≥n whenever uv is not an arc of T,and have a vertex w to uw and wv are two arc of T.In this paper an p×q bipartite tournament T satisfies the condition G（n） and strong was discussed,then T at least contains 2 min{n＋1,p,q} cycles,unless T is even is omorphic to a sepcified family of graphs B（k1,k2,k3,n/2）,ki≥n/2,i=1,2,3.

关 键 词：有向图 竞赛图 强连通 HAMILTON圈 

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