几乎正则多部竞赛图的点泛圈性

令T是多部竞赛图;i（T）=|d+（x）-d-（y）|（这里允许x=y）,如果i（T）=0,则T被称为是正则的;如果i（T）≤1,则T被称为是几乎正则的.Volkmann猜测几乎正则c-部竞赛图（c≥4）是泛圈的.本文证明当c≥5时,除了有限多个几乎正则多部竞赛图外,所有几乎正则c-部竞赛图都是点泛圈的.同时我们给出一个反例说明当c=4时,上述猜想不成立.     

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

Guo(Discrete Appl.Math.95(1999)273-277)提出外路的概念.有向图中一个顶点x(或弧xy)的一条外路是指起始于x(或弧xy)的一条路使得x控制这条路的终点仅当终点也控制x.一条长为k的外路称为k-外路.本文证明了一个几乎正则c-部(c≥8)竞赛图D中,如果D的每个部集至少包含两个点,则D中每条弧有(k-1)-或k-外路,其中k∈{3,4,…,|V(D)|-1}.进一步,当D是一个几乎正则c-部(c≥8)竞赛图,且每个部集所含顶点数目相同时,D的每条弧在k-或(k+1)-圈中,其中k∈{3,4,…,|V(D)|-1}.     

正则多部竞赛图中任意弧的所有长度的外路

多部竞赛图D中弧x_1x_2的一条(l-1)一外路是指起始于x_1x_2的长为l-1的路x_1x_2…x_1,其中要么x_1与x_1同部,要么x_1控制x_1.特别地,当l=|V(D)|且x_1控制x_1时,x_1x_2…x_lx_1是一个通过弧x_1x_2的Hamilton.Guo(Discrete Appl.Math.95(1999)273-277)证明了一个正则c-部(c≥3)竞赛图中的每条弧都有一个(k-1)-外路,其中k∈{3,4,…,c}.作为一个推广,该文证明了一个正则c-部(c≥5)竞赛图中的每条弧都有一个(k-1)-外路,其中k∈{3,4,…,|V(D)|}.进一步,使用路收缩技巧,下面一个结果也被证明:D是一个正则c-部(c≥8)竞赛图,且每个部集包含两个顶点,则D的每条弧被包含在一个Hamilton圈中.这个结果部分地支持了Volkmann和Yeo(Discrete Math.281(2004)267-276)提出的猜想:正则多部竞赛图的每条孤都包含在一个Hamilton圈中.     

正则多部竞赛图中过任意点的强子竞赛图

对正则多部竞赛图中的强子竞赛图进行了研究,证明了正则c(c≥6)部竞赛图中每点都在顶点数为{3,4,…,c-3}的强子竞赛图中.     

正则多部竞赛图的控制图

设D=(vA)是一个有向图,x,y∈V(D),记O(x)是x控制的顶点的集合,如果O(x)∪O(y)∪{x,y}=V(D),则称x和y控制D.有向图D的控制图记为dom(D),它是—个无向图,顶点集是V(D),且对x,y∈V(D),xy是dom(D)的一条边当且仅当x和y控制D.1998年,Fisher等人首次提出控制图的概念,并完全刻画了竞赛图的控制图.本文研究正则多部竞赛图的控制图,并给出了—个无向图是某个正则多部竞赛图的控制图的一个刻画.     

正则多部竞赛图的竞争指数

设D是一个有向图,若存在无向图G满足:(1)G的顶点集与D的顶点集相同;(2)任取D中的两个顶点x,y,其在G中相邻当且仅当存在D中顶点z,使得D中包含一条从x到z的长为m的有向途径和一条从y到z的长为m的有向途径,则称G为D的m步竞争图,记为G=C~m(D).2004年,Cho和Kim首次提出竞争指数的概念.若对于某个正整数r和所有非负整数i,存在最小正整数q,使C~(q+i)(D)=C~(q+i+r)(D),则称整数q为D的竞争指数,记为cindex(D).2008年,Kim给出了竞赛图的竞争指数的上界.2009年,Akelbek和Kirkland给出了本原有向图的竞争指数.文中研究并计算了正则多部竞赛图的竞争指数.     

一个不等式的推广

本刊文[1]给出如下姊妹不等式:若a,b,c是正数,且a b c=1,则有1b c-ac 1a-ba 1b-c≥673(1)当且仅当a=b=c=31时取等号.1b c ac 1a ba1 b c≥1613(2)当且仅当a=b=c=31时取等号.不等式(1)可改写为:11-a-a1-1b-b1-1c-c≥673(3)当且仅当a=b=c=31时取等号.本文将把不等式(3)推广为:命题设xi>0(i=1,2,…,n),∑ni=1xi=1,则∏ni=1(1-1xi-xi)≥(n-n1-1n)n(4)当且仅当x1=x2=…=xn=1n时等号成立.引理设f″(x)>0,则1n∑ni=1f(xi)≥f(1ni∑=n1xi)(5)此即著名的Jesen不等式.下面给出(4)式的证明.证设y=f(x)=ln(1-1x-x)(0相似文献   

1990年苏州市高中数学竞赛试题与解答

.犷一护2 一、选择题: 1.如果12卜i,0是z的幅角,那么当:变化时,Z二:2 2沈050在复平面上对应点的轨迹是: (A)圆,(B)双曲线;(C)抛物线;(D)两条相交直线. 答(A)和c(x一g)关于s(x),c(x)、s(y)、e勿)的表达式分别为s(x一夕)=s(x)c(y)一c(x)s(y)e(x一y)=c(x)e(夕)一s(x)s(夕)X:a2动直线ux ,y 工=O截已知椭圆、=1于点尸、Q,已知点口为椭圆的 2.如图ABCD为空间四边形,G、E在BC上,F、H在AD上,图中异面直线共有:(A)7对;(丑)8对;B(C)9对,(D)10对.中心,艺P口Q二则:,十,“=丰90“,则 1宁几孟-.. b‘-EG 答(C) 3。不定方程Zx 3夕=。(n任N)的…     

一对姐妹不等式的简证和再推广

文[1]提出并证明了下面一对姐妹不等式:若a,b,c是正数,且a b c=1,则有1b c-ac 1a-ba1 b-c≥763,①1b c ac1 a ba1 b c≥1613.②以上两式当且仅当a=b=c=31时取等号.但文[1]证明过程较繁杂,本文给出一种简单证法,并将结论进行一定推广.1一对不等式的简证先证上述不等式①.记x=b c,y=c a,z=a b,则有00,即f(t)为下凸函…     

关于丢番图方程(an)x+(bn)y=(cn)z

设n,a,b,c是正整数,gcd(a,b,c)=1,a,b≥3,且丢番图方程a~x+b~y=c~z只有正整数解(x,y,z)=(1,1,1).证明了若(x,y,z)是丢番图方程(an)~x+(bn)~y=(cn)~z的正整数解且(x,y,z)≠(1,1,1),则yzz或xzy.还证明了当(a,b,c)=(3,5,8),(5,8,13),(8,13,21),(13,21,34)时,丢番图方程(an)~x+(bn)~y=(cn)~z只有正整数解(x,y,z)=(1,1,1).