扩充竞赛图的(1,2)步竞争图

2011年Factor等人提出了有向图的(1,2)步竞争图的概念,并完全刻画了竞赛图的(1,2)步竞争图.设D=(V,A)是一个有向图.如果无向图G=(V,E)满足,V(G)=V(D)并且xy∈E(G)当且仅当D中存在顶点z≠x,y使得d_(D-y)(x,z)=1,d_(D-x)(y,z)≤2或者d_(D-x)(y,z)=1,d_(D-y)(x,z)≤2,那么称G为D的(1,2)步竞争图,记为C_(1,2)(D).本文主要刻画了扩充竞赛图的(1,2)步竞争图.     

正则多部竞赛图的控制图

设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给出了本原有向图的竞争指数.文中研究并计算了正则多部竞赛图的竞争指数.     

(i,k)-步直觉模糊和双极模糊竞争图

直觉模糊竞争图和双极模糊竞争图是有向图的竞争图的推广.2015年Alshehri和Akram引入了m-步双极模糊竞争图的概念.2016年,Sahoo和Pal引入了m-步直觉模糊竞争图的概念.本文引入(i,k)-步直觉模糊竞争图和(i,k)-步双极模糊竞争图的概念,给出并证明(i,k)-步直觉模糊竞争图中边独立强的一个条件,证明对直觉模糊有向图D或双极模糊有向图D有CC(D_(i,k))=C_(i,k)(D),并分别描述(i,k)-步直觉模糊竞争图在生态系统中和(i,k)-步双极模糊竞争图在社会群体中的应用.     

有向图的L(j,k)数的上界

给定正整数j≥k,有向图D的一个L(j,k)-标号是指从V(D)到非负整数集的一个函数f,使得当x在D中邻接到y时|f(x)-f(y)|≥j,当x在D中到y距离为二时|f(x)-f(y)|≥k.f的像元素称为标号.L(j,k)一标号问题就是确定(?)j,k-数(?)j,k(D),这个参数等于(?) max{f(x)|x∈V(D)},这里f取遍D的所有L(j,k)-标号.本文根据有向图的有向着色数及最长有向路的长度来研究(?)j,k-数,证明了:(1)对任何有向着色数为(?)(D)的有向图D,(?)j,k(D)≤((?)(D)-1)j;(2)对任何最长有向路的长度为l的有向图D,如果不含有向圈或者D中最长有向圈长度为l 1,则(?)j,k(D)≤lj.并且这两个界都是可达的.最后我们对l=3的有向图给出了3j-L(j,k)-labelling的一个有效算法.     

有向路和有向圈的控制集数

1引言设G=(V,E)为无向图．子集D (?)V(G)是无向图G的控制集,如果对于任意的y,∈V(G)-D,都存在x∈D,使xy∈E(G)．G的控制集D是G的分裂控制集,如果G中由V(G)-D导出的子图G〈V(G)-D〉是不连通的．G的一个控制集D是G的一个强(弱)控制集,若dG(x)≥d_G(y)(d_G(x)≤d_G(y)),其中d_G(x)表示G中与点x关联的边数．对于有向图H=(V,A),子集D(?)V(H)称为H的控制集,如果对于任意的y∈     

三路树P(m,n,t)是边幻图的证明(Ⅱ)

令简单图G=(V,E)是有p个顶点q条边的图.假设G的顶点和边由1,2,…,p+q所标号,且f:V ∪E→{1,2,…,p+q}是一个双射,如果对所有的边xy,f(x)+f(y)+f(xy)是常量,则称图G是边幻图(edge-magic).本文证明了三路树P(m,n,t)当n为偶数,t=n+2时也是边幻图.     

一道国际竞赛题的简证

题目:(2006年土耳其国家队选拨考试)已知正数x,y,z满足xy yz zx=1,证明:247(x y)(y z)(z x)≥(x y y z z x)2≥63.文[1]采用三角换元法,并利用导数和Jensen不等式给出了证明.274(x y)(y z)(z x)≥(x y y z z x)2.但证明过程中错证了cosA cosB cosC≤323.从而证明247(x y)(y z)(z x)≥(x y y z z x)2的证法是错误的.下面给出一个简证.证明:先证(x y)(y z)(z x)≥98(x y z)(xy yz zx)①上面不等式等价于(x y z)(xy yz zx)-xyz≥98(x y z)(xy yz zx)(x y z)(xy yz zx)≥9xyz.由A—G不等式有x y z≥33xyz,xy yz zx≥33x2y2z2,故(x y z)(xy yz…     

图C_5∨K_t的邻点可区别全色数

设f是图G的一个正常全染色.对任意x∈V(G),令C(x)表示与点x相关联的边的颜色以及点x的颜色所构成的集合.若对任意uv∈E(G),有C(u)≠C(v),则称.f是图G的一个邻点可区别全染色.对一个图G进行邻点可区别全染色所需的最少的颜色的数目称为G的邻点可区别全色数,记为Xat(G).用C_5∨K_t表示长为5的圈与t阶完全图的联图.讨论了C_5∨K_t的邻点可区别全色数.利用正多边形的对称性构造染色以及组合分析的方法,得到了当t是大于等于3的奇数以及t是偶数且2≤t≤22时,X_(at)(C_5 V K_t)=t+6,当t是偶数且t≥24时,X_(at)(C_5 V K_t)=t+7.     

一道2000年IMO试题的高等数学背景

我们首先给出 2 0 0 0年第 41届 IMO之第2题及其解答 [1] :设 a、b、c是正数 ,满足 abc =1 .证明( a- 1 1b) ( b- 1 1c) ( c- 1 1a)≤ 1 .证明　令 a =xy、b =yz、c =zx,其中x、y、z为正数 ,则原不等式变为( x - y z) ( y - z x) ( z - x y)≤ xyz ( 1 )显然 x - y z、y - z x、z - x y里最多又有一个是负数 .如果恰有一个是负数 ,那么 ( 1 )式显然成立 ;如果这三个数都非负 ,那么根据算术平均—几何平均可得　 ( x - y z) ( y - z x)≤ 12 [( x - y z) ( y - z x) ]=x　 ( y - z x) ( z - x y)≤ 12 [( …     

三角形不等式的共同解法—关于三角形旁切圆半径的两个不等式证明的改进

众所周知(x y)(y z)(z x)=xy(x y) yz(y z) zx(z x) 2xyz=x2y xy2 y2z yz2 z2x zx2 2xyz　(*)这是一个十分重要的代数恒等式,由(*)立即得到(x y)(y z)(z x)=(x y z)(xy yz zx)-xyz(1)(x y)(y z)(z x)=x(y z)2 y(z x)2 z(x y)2-4xyz(2)(x y)(y z)(z x)(x y z)=xy(x y)2 yz(y z)2 zx(z x)2 4xyz(x y z)(3)(x y)(y z)(z x)(xy yz zx)=x2y2(x y) y2z2(y z) z2x2(z x) 2xyz(x y z)2(4)……(*)及(1),(2),(3),(4)……在证明关于三角形不等式方面有极其广泛的应用.这是因为:图1任一三角形总有内切圆(图1),总可以作变换a=y z,b=z x,c=x y(x,y,z∈R )…     

图中推广的正交因子分解

设G是一个图,具有顶点集合V(G)和边集合E(G).设g和f是定义在V(G)上的整数值函数,使对每个x∈V(G),有g(x)≤f(x).图G的一个(g,f)-因子是G的一个支撑子图H,使对每个x∈V(G),有g(x)≤d_H(x)≤f(x).G的一个(g,f)-因子分解是E(G)的边不相交的(g,g)-因子的一个划分.设F={F-1,F_2,…,F_m}为G的一个因子分解,H是G的一个有mr条边的子图.如果每个F_i恰好与H有r条公共边,1≤i≤m,则称Fr-正交于H.本文证明每个(mg+kr,mf-kr)-图含有一个子图R,使R有(g,f)-因子分解r-正交于任意给定的有kr条边的子图,其中m,k和r为正整数且k相似文献   

f—因子覆盖的图

设G为图,f是定义在V(G)上的正整数值函数。称图G的支撑子图F为f-因子如果d_(?)(x)-f(x),x∈V(G).称图G是f-因子覆盖的如果G的每条边包含在一个f-因子中.本文给出了一个图是f-因子覆盖的图的充要条件,其结果推广了C.H.C.Little et al.[1]的1-因子覆盖定理。     

关于加权距离正则图和立方图

令G=(V,E)是简单的连通k-正则图;w_1相似文献   

三路树P(m,n,t)是边幻图的证明(II)

令简单图G=(V,E)是有p个顶点q条边的图.假设G的顶点和边由1,2,…,p+q所标号,且f:V∪E→{1,2,…,p+q}是一个双射,如果对所有的边xy,f(x)+f(y)+f(xy)是常量,则称图G是边幻图(edge-magic).本文证明了三路树P(m,n,t)当n为偶数,t=n+2时也是边幻图.     

图在三种约束条件下的正常全染色

设f:V(G)∪E(G)→{1,2,…,k}是简单图G的一个正常k-全染色.令C(f,u)={f(e):e∈N_e(u)},C[f,u]=C(f,u)∪{f(u)},C_2[f,u]=C(f,u)∪{f(x):x∈N(u)}∪{f(u)}.N(u)表示顶点u的邻集,N_e(u)表示与顶点u的相关联的边的集合.令C[f;x]={C(f,x);C[f,x];C_2[f,x]},对任意的xy∈E(G),G[f;x]≠C[f;y]表示C(f,x)≠C(f,y),C[f,x]≠C[f,y],C_2[f,x]≠C_3[f,y]同时成立.对任意的边xy∈E(G),如果有C[f;x]≠C[f;y]成立,则称f是图G的一个k-(3)-邻点可区别全染色(简记为(3)-AVDTC).图G的(3)-邻点可区别全染色中最小的颜色数叫做G的(3)-邻点可区别全色数,记为x_((3)as)″(G).研究了联图,完全二部图的(3)-邻点可区别全染色,得到了它们的(3)-邻点可区别全色数.     

有约束条件的图的(g,f)-因子

设G是一个图,用V(G)和E(G)表示它的顶点集和边集,并设g和f是定义在V(G)上的两个整数值函数且g＜f.图G的一个(g,f)-因子是G的一个支撑子图F使对任意的x∈V(G)有g(x)≤dF(x)≤f(x).如果过图G的任意k条边都有一个(g,f)-因子,则称图G是一个(g,f)-k-覆盖图.如果图G的任意k条边不属于它的一个(g,f)-因子,则称图G是一个(g,f)-k-消去图.作者分别给出了一个图是(g,f)-k-覆盖图和(g,f)-k-消去图的充分条件.     

消去图、覆盖图和均匀图的若干结果

设 G是一个图 ,g,f是定义在图 G的顶点集上的两个整数值函数 ,且g≤f.图 G的一个 ( g,f) -因子是 G的一个支撑子图 F,使对任意的 x∈V( F)有g( x)≤ d F( x)≤ f ( x) .文中推广了 ( g,f) -消去图、( g,f ) -覆盖图和 ( g,f) -均匀图的概念 ,给出了在 g相似文献   

对于X-join不可分解的无三角形的图

本文中的图都是有限简单图.仅含一个点的图叫作平凡图,不含边的图叫作空图.V(G)与 E(G)分别表示图 G 的点的集合与边的集合.有时以 G 代替 V(G),以 x∈G代替 x∈V(G).对 x∈G,N_G(x)={y∈G|xy∈E(G)}叫作 x 的邻域.下面的概念是 Sabidussi 引入的:令{G_x|x∈X}是图的一个族,指标取自另一个图 X.令#表示 X 中的邻接关系,⊥_x表示 G_x 中的邻接关系,则这一族图的 X-join 是指图 G,G=(?)(G_x×{x}),且 G 中的邻接关系⊥定义为:对 G 中任两个点(a,r)与(b,s),(a,r)⊥(b,s)当且仅当 r#s 或r=s 且 a⊥_rb.     

准传递定向图上的Seymour点

有向图D是准传递的,如果对D中任意三个不同的顶点x, y和z,只要在D中存在弧xy, yz, x和z之间就至少存在一条弧. Seymour二次邻域猜想为:在任何一个定向图D中都存在一个顶点x,满足d_D~+(x)d_D~(++)(x).这里,定向图是指没有2圈的有向图.称满足Seymour二次邻域猜想的点为Seymour点. Fisher证明了Seymour二次邻域猜想适用于竞赛图,也就是每个竞赛图至少包含一个Seymour点. Havet和Thomassé证明了,无出度为零的点的竞赛图至少包含两个Seymour点.注意到,竞赛图是准传递有向图的子图类.研究Seymour二次邻域猜想在准传递定向图上的正确性,通过研究准传递定向图与扩张竞赛图的Seymour点之间的关系,证明了准传递定向图上Seymour二次邻域猜想的正确性,得到:每个准传递定向图至少包含一个Seymour点;无出度为零的点的准传递定向图至少包含两个Seymour点.