扩充竞赛图的控制图

设D=(V,A)是一个有向图,对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。文章研究扩充竞赛图的控制图,并给出了求解扩充竞赛图的控制图的一个算法。     

圈的幂图的s-迹连通性

对于图G的任意两个顶点x和y,如果G有一条(x,y)-生成迹,则称图G是迹连通的。给定一个整数s≥0,对于任意点子集X?V(G)并且|X|≤s,如果G-X是迹连通的,则称图G是s-迹连通。设k是一个正整数,图G的k次幂图记为G~k。设t(G)是t一个最大值s使得图G是s-迹连通但不是(s+1)-迹连通,设C_n是一个包含n个点的圈,k是一个正整数并且k≥2,将证明:t(C_n~k)={2k-3,如果n=2k+2 2k-2,如果n≥2k+3 n-3,如果n≤2k+1     

竞赛图的零因子半群

讨论了竞赛图的零因子半群.一个半群S的零因子图是一个有向图Γ(S),其顶点是S中非零的零因子,S中两个不同的元x,y有一条有向边x→y当且仅当xy=0.该文证明了如果S是一个没有非零幂零元的有限半群且图Γ(S)的顶点数大于1,那么图Γ(S)不是一个竞赛图.另外对于任意的正整数n,该文完全决定了顶点数为n蹬任一个竞赛图的所有零因子半群.     

距离为2的邻集并条件与图的泛连通性

设G是一个顶点数为n(≥5)最小度为δ的2-连通简单图．本文证明了若图G的每一对距离为2的顶点u,v都满足|N(u)∪(v)|≥n-δ 1,则除非G属于某些特殊图类,它的任意一对顶点x,y之间都存在长度从d(x,y)到n-1的路．     

关于丢番图方程(na)x+(nb)y=(nc)z(c=65,89,101)

设a,b,c为两两互素的正整数且满足a2+b2=c2.1956年,Je?manowicz猜测丢番图方程(na)x+(nb)y=(nc)z仅有正整数解x=y=z=2.此利用初等方法证明了:对于任意的正整数n,除去x=y=z=2外,丢番图方程(56n)x+(33n)y=(65n)z,(80n)x+(39n)y=(89n)z和(20n)x+(99n)y=(101n)z无其他的正整数解,即当(a,b,c)=(56,33,65),(80,39,89)和(20,99,101)时,Je?manowicz猜想成立.     

关于二分图的一点注记

在讨论Matroid理论时,我们遇到了下述的图论问题:设G=(X∪Y,E)是一个二分图,对G的任一顶点a,以Γ(a)表示a的邻点集,以v(a)表示a的邻点个数。φ是X到X的一个映射,满足: φ[φ(x)]=x,x∈X。如果对图G我们只知道对x∈X当y∈Γ(x)时v(y)v[φ(x)]之间有一定的关系,从这种关系希望能够推算出|X|与|Y|谁大谁小来,这里|X|与|Y|分别表示顶点集X与Y的顶点个数。现在叙述有关这一问题的若干结果。     

关于竞赛图的弧k-反回路性质

设T=(▽,A)是一个竞賽图.|▽|=p称T具有P_k(p′_k)性质,若 xy∈A,T中存在一条长度为k-1的y-x路(x-y路),其中2≤k相似文献   

关于丢番图方程(16n)~x+(63n)~y=(65n)~z

设n是正整数,运用初等方法证明了丢番图方程(16n)x+(63n)y=(65n)z仅有整数解(x,y,z)=(2,2,2),从而得到了Jesmanowicz猜想在该情形下成立.     

有关偏序集与竞赛图的讨论

给定一个竞赛图T=(V，A)，与T相关联的偏序集P是一个偏序集P1=(V，≤)，使得V．x，y∈V(T)，x≤y当且仅当x=y或者d(x，y)≥3．证明了每一个竞赛图都与一个偏序集相关联，但存在偏序集不与任何竞赛图相关联．此外，还对与竞赛图相关联的偏序集的性质进行了讨论．     

关于丢番图方程(na)x+(nb)y=(nc)z(c=181,845)的解

研究了Jes'manowicz提出的关于丢番图方程(na)x+(nb)y=(nc)z的解的猜想.利用数论中的一些方法,得到了丢番图方程(19 n)x+(180 n)y=(181 n)z和(837 n)x+(116 n)y=(845n)z的所有整数解,证明了Jes'manowicz猜想在这两种情形下的正确性.     

图是超级限制性边连通的一个Ore型充分条件

设G是n阶简单无向图,G的顶点x的度记为d(x)。证明了如果对G中每一对不相邻的顶点x和y都有d(x) d(y)≥n＋2,那么,G是超级限制性边连通的,除非n≥6是偶数且G＝2Kn/2∪F2,这里F2是G的一个2因子,这一结果是对图的极大限制性边连通性的Ore型充分条件的进一步扩展。     

二分图中度条件与[a,b]-覆盖图

设G是一个图,用V(G)和E(G)表示它的顶点集和边集,并设g和f是定义在V(G)上的两个整数值函数且g相似文献   

完全四部图的色性

设G是一个图，P(G，λ)是G的色多项式．若P(G，λ)=P(H，λ)，则称G和H是色等价的，简单地用G～H表示．令[G]={H\H～G)．若[G]={G)，称G是色唯一的．用G=K(n1，n2，n3，n4)表示完全四部图且2≤n1≤n2≤n3≤n4，得到了[G]С{K(x，y，z，w)-S｜z y w =n1 n2 n3 n4,1≤z≤y≤z≤w≤n4-1，或1≤x≤y≤z≤n3-1和w=n4U{G}，其中S是K(x，y，z，w)的某s条边组成的集合且K(x，y，z，w)-s表示从K(x，y，z，w)中删去S中所有边得到的图．从而证明了当n≥k 2，t≥2时，K(n-k，n，n，n)是色唯一的．     

图的周长

设G为n阶2连通图,D(x)={y|y∈V(G)~\(x),d(x,y)≤2},δ_o=min{max{d(x),d(y)}|x,y∈V(G),d(x,y)=2},D(δ_o)={x|x∈V(G),d(x)≥δ_o},δ~*为G中的顶点度且满足:(Ⅰ)δ~*尽可能的大,(Ⅱ)对经(?)x∈D(δ_o)及D~*(x)={y|y∈(D(x)∪{x}),d(y)<δ~*}有|D~*(x)|相似文献   

二分图中相互独立的圈

证明了下面的结论：设k≥1是一个整数，G＝（V1,V2；E）是一个二分图，满足|V1|=|V2|=n≥2k 1。若对G中任意两个不相邻的面点x∈V1，y∈V2，都有d(x) d(y)≥2k 2，并且δ（G）≥2，则G包含k个相互独立的图。     

多部竞赛图的点泛圈性

把c-部完全图的每条边任意加上一个方向后得到的定向图称为c-部竞赛图,设T为c-部竞赛图,定义ig(T)=maxx,y∈VCT│d^ (x)-d^-(y)│。给出了c－部竞赛图具有点泛圈性的一个充分条件,即：设T为c－部竞赛图（c≥13),V1,V2,…Vc为T的各分部。如果│V1│≤│V2│≤…≤│Vc│≤│V1│ 1并且ig(T)≤1,那么T具有点泛圈性。     

特殊二部图的上可嵌入性

探讨二部图的上可嵌入性,证明了如下结果：(1)设G=(X,Y；E),定义G~3=(V(G~3),E(G~3)),其中V(G~3)=V(G),E(G~3)=E(G)∪{e=xy|d_G(x,y)：3,x∈X,y∈Y},则G~3是上可嵌入的；(2)设G=(X,Y；E),|X|=|Y|=n(n≥3),对任一对d_G(x,y)=3的x∈X,y∈Y,均有d(x) d(y)≥n 1,则G是上可嵌入的。     

关于丢番图方程(65n)~x +(72n)~y =(97n)~z

本文证明了对任意的正整数n,丢番图方程(65n)x+(72n)y=(97n)z仅有正整数解(x,y,z)=(2,2,2).     

一类广义超特殊p-群的因子分解数

设G是一个有限群,A,B是G的两个子群,若G=AB,则称G被A和B因子分解.设G是如下的一类广义超特殊p-群,G=,m≥1,则G的因子分解数被确定.     

关于丢番图方程(45n)~x+(28n)~y=(53n)~z的解

利用初等方法证明了,对于任意的正整数n,丢翻图方程(45n)x+(28n)y=(53n)z仅有x=y=z=2正整数解.