奇阶完备残差图

本文讨论奇阶完备残差图,证明了对于任意奇数n,不存在奇阶Kn-残差图.对任意奇数t≥3和n=2t,2t -2,2t-4构造了一类具有奇阶2n+t的Kn-残差图.我们证明了当n≡0(mod4)时,Kn-残差图的最小奇阶为5n/2+1;当n≡2(mod4)时,Kn-残差图的最小奇阶为5n/2,并且证明了相应的最小奇阶Kn-残差图的唯一性.     

The nonorientable genus of the join of two cycles

In this paper, we show that the nonorientable genus of Cm ＋ Cn, the join of two cycles Cm and Cn, is equal to [（（m-2）（n-2））/2] if m = 3, n ≡ 1 （mod 2）, or m ≥ 4, n ≥ 4, （m, n） （4, 4）. We determine that the nonorientable genus of C4 ＋C4 is 3, and that the nonorientable genus of C3 ＋Cn is n/2 if n ≡ 0 （mod 2）. Our results show that a minimum nonorientable genus embedding of the complete bipartite graph Km,n cannot be extended to an embedding of the join of two cycles without increasing the genus of the surface.     

有向图4-→Cn的优美性

研究了有向图m→C n 的优美性,利用搜索图的标号的算法与数学证明相结合的方法,证明了有向图4→ Cn 为优美图,其中n为任意正整数。     

关于图P3n优美性的研究

在n个顶点的路Pn上,当且仅当两点的距离为3时增加一条边,所得的图称为P3n,本文给出了图P3n(n≥4)的优美标号,从而证明了P3n都是优美图.     

关于图P_n~3优美性的研究

在n个顶点的路Pn上,当且仅当两点的距离为3时增加一条边,所得的图称为P3n,本文给出了图P3n(n≥4)的优美标号,从而证明了P3n都是优美图.     

可平面图的线性2-荫度的新上限（英文）

图G的线性2-荫度,记作la_2(G),是使得图G能够被剖分成k个边不交森林的最小正整数k,其中每个森林的每棵树是长度至多为2的路.本文给出了可平面图和没有三角形的可平面图的线性2-荫度的新上界,即证明了:(1)对于一般可平面图,当△≡0,3(mod 4)时,la_2(G)≤[△/2]+9;当△≡1,2(mod 4)时,1a_2(G)≤[△/2]+8;(2)对于不含三角形的可平面图,当△≡0,3(mod 4)时,la_2(G)≤[△/2]+5;当△≡1,2(mod 4)时,la_2(G)≤[△/2]+6;其中△为图G的最大度.     

伪完全二分图PK_(n,n)奇优美标号的计算机实现

给出了伪完全二分图PK_(n,n)的定义及性质,提出了该类图的奇优美标号算法,证明了算法的正确性及时间复杂度,从而证明了伪完全二分图的奇优美性.并给出了伪完全二分图PK_(n,n),当n=3,4,5的一种标号方法.     

图P_m×C_n和W(m,n)的序列性

给出了图Pm×Cn,I(Pm×Cn)和W(m,n)的序列标号.证明了图Pm×Cn,I(Pm×Cn)和W(m,n)(m≥1,n≥3且n为奇数)是序列图,从而也是调和图.     

→Pn和→Cn的有向优美性

优美图可用在图论中的某些H-分解问题中,很多人研究无向图的优美标号.研究有向优美标号,通过对阶数奇偶性的讨论,给出了n(≥2)阶有向路(→Pn)和n(≥3)阶有向圈(→Cn)是有向优美的充分条件.     

P(n,2)的符号全加强数

图G的符号全加强数的定义为:对于E~c(G)中的任意一子集S,使得不等式γ_s~t(G+S)γ_s~t(G)成立的最小的集合S的势.给出了一般Petersen图P(n,2)的符号全加强数:对于任一正整数n≥6,当n三2(mod 3)时,R_s~t(P(n,2))=2;当n≡1(mod 3)时,R_s~t(P(n,2))=3;当n≡0(mod 3)时,R_s~t(P(n,2))=5.     

关于有向图n·_3是优美图的一个猜想的证明

在文 [1 ]中提出猜想 :当 n≡ 0 (mod2 )时 ,n· C 3是优美图 .本文证明了这个猜想 .     

任意n个完备二分图的并图的k－优美性和算术性

证明了对于正整数k,n,si,ti（si,ti≥2,i=1,2,…,n）,图n/U/i=1,Ksi,ti是k-优美图;对于正整数k,d（d≥2）,k≠0（roodd）及n,si,ti（si,ti≥2,i=1,2,…,n）,图n/U/i=1,Ksi,ti是（k,d）-算术图,前一结论推广了文[6]的相应结果。     

一类优美图

设u、ν是两个固定顶点.用b条内部互不相交且长度皆为a的道路连接u、ν所得的图用P_a,b表示.KM.Kathiresan证实P_2,2m-1(r,m皆为任意正整数)是优美的,且猜想:除了(a,b)=(2r+1,4s+2)外,所有的P_a,b都是优美的.杨元生已证实P_2r+1,2m-1是优美的,并且证实了当r=1,2,3,4时的P_2r,2m也是优美的.本文证实r=5,6,7时P_{2r,2m相似文献}   

Simply sequentially additive labelings of 2-regular graphs

We conjecture that any 2-regular simple graph has an SSA labeling. We provide several special cases to support our conjecture. Most of our constructions are based on Skolem sequences and on an extension of it. We establish a connection between simply sequentially additive labelings of 2-regular graphs and ordered graceful labelings of spiders.     

有向图3C2p的优美性

图论是数学的一个分支,特别是离散数学的一个重要分支,它在物理、化学、天文、地理、生物学,尤其是在计算机科学中有着非常广泛的应用．图的标号问题是图论中极有趣的一个研究课题,有着较好的研究价值和广阔的应用背景．图的一个顶点标号是顶点集合到非负整数集合的映射,而边标号是边集合到非负整数集合的映射,根据对映射的不同要求,产生了各种各样的图的标号问题,有向图的优美标号是其中的一类．用G表示有n个顶点的有向圈,mCn表示m个无公共顶点的有向圈G之并,本文研究了有向图mG,的优美性,利用搜索图的标号的算法与数学证明相结合的方法,证实了有向图3Cn为优美图,其中n=2p,P为任意正整数．     

具有匹配对网络模型的优美性

在当今网络研究中,人们需要将某些特殊的图分解为指定的结构.优美图可以被运用到图分解中.得到一些构造优美图的可算法化的方法,并构造较为复杂的优美图.     

有向图n·■_m的优美性

给定有向图D(V,E),如果存在一个单射f:V(D)→{0,1,…,|E|}使得对于每条有向边(u,v),诱导函数f′:E(D)→{1,2,…,|E|}是一个双射函数,其中,f′(u,v)=[f(v)-f(u)](mod(|E|+1)),则f称为有向图D(V,E)的优美标号,f′称为有向图D(V,E)的诱导的边的优美标号.本文讨论了有向图n.■m的优美性,并且证明了当m=23且n为偶数时,n.■m是优美有向图.     

关于联图P_1VP_n的k-强优美性

本文研究了联图P_1VP_n的k-强优美性问题.利用K-强优美图的定义,获得了联图P_1VP_n是k-强优美图的必要条件,还得到了当n:2k-1时联图P_1VP_n是k-强优美图,亦是k-优美图,及当n≥3时联图P_1VP_n是2-强优美图,也是2-优美图的结果,推广了联图P_1VP_n是优美图的结果.