区组长度为{3,4}的自反Mendelsohn设计和自反强制Mendelsohn设计

一个Mendelsohn设计MD(v,k,λ)称为是自反的,记为SCMD=(v,k,λ)=(X,B,f),如果存在从(X,B)到(X,B-1)的同构映射f,B-1={B-1;B∈B},其中若B=则B-1=.当λ=1时记作k-SCMD(v).一个{k1,k2}-SCMD(v)称为是自反强制Mendelsohn设计,记作{k1,k2}-SCMMD(v),若{k1,k2}-SCMD(v)中区组长度至少有一个k1和一个k2.该文给出了{3,4}-SCMD(v)和{3,4}-SCMMD(v)的存在性.     

Zv上(v,k,k-1)-不相交差族的构造方法

给出了不相交差族的3种新构造方法:利用循环的B(k,1;v)(即CB(k,1;v));利用循环的GDD及半循环的frame;当p≡5 (mod 12)为素数时,Z5p上的(5p,3,2)-DDF有一种特殊的构造方法.并得到了参数为(v,3,2)和(v,4,3)的不相交差族的一些新结果.     

星和扇上的锥的D(2)-点可区别正常边染色

设G是顶点集合为V(G)={v0i|i=1,2,…,p}的简单图,n是正整数,称Mn(G)为G上的锥(或广义Mycielski图),如果V(Mn(G))={v01,v02,…,v0p;v11,v12,…,v1p;…,vn1,vn2,…,vnp,w},E(Mn(G))=E(G)∪{vijv(i 1)k|v0jv0k∈E(G),1≤j,k≤p,i=0,1,…,n-1}∪{vnjw|1≤j≤p}.在这篇文章里,我们讨论了星和扇上的锥的D(2)-点可区别的正常边染色,并给出了相应色数.     

一类亚几乎唯一泛圈图

设G是阶为n的简单Hamilton图,若存在不同的p,q(3≤p相似文献   

区组长为4的自反有向平衡不完全区组设计

如果从一个有向平衡不完全区组设计DB(k,λ;v)(X,B)到(X,β-1)之间存在一个同构映射f,则这个DB(k,λ;v)被称为自反的,记为SCDB(k,λ;v)(X,β,f),其中β-1={B-1:B∈B},当B=(x1,x2,…,xk-1,xk)时B-1=(xk,xk-1,…,x2,x1).本文主要证明了SCDB(4,λ;v)存在的充分必要条件是λ≡1,2(mod 3)时,v≡1(mod 3)且v≥4,(v,λ)≠(7,1);λ≡0(mod 3)时,v为≥4的任意整数.     

无K_(1,t)图的L(d,1)-T标号

给定一个连通图G=(V,E)及其一棵支撑树T,图G的一个L(d,1)-T标号即函数g:V(G)→{0,1,2,…},满足:(1)如果xy∈E(G),则|g(x)-g(y)|≥1;(2)如果dG(x,y)=2,则|g(x)-g(y)|≥1;(3)如果xy∈E(T),则|g(x)-g(y)|≥d.假设图G有一个L(d,1)-T标号函数g:g(V){0,1,2,…,k},则图G的所有L(d,1)-T标号函数中最小的整数k记为L(d,1)-T标号数λdT(G,T).本文证明了若G是无K1,t(3≤t≤n)的连通图,其最大度为Δ,|G|=n,T为G的任意支撑树,则λdT(G,T)≤tt--12Δ2+Δ+2d-2.     

Halin图的列表L(p,q)标号

图G的一个列表L,是指对G的每一个顶点v指定的一个标号集合L(v)。G的一个列表L(p,q)-标号是G的一个正常L(p,q)-标号,使得每一个顶点v∈V(G)均可在其对应的列表L(v)里选取一个标号。G的一个k-列表L(p,q)标号是一个列表L(p,q)-标号,使得G的所有顶点v的列表L(v)的长度L(v)=k 1。定义G的列表L(p,q)-标号数λl(G)=m in{G k有一个k-列表L(p,q)-标号}。讨论了Halin图的列表L(p,q)-标号问题,证明了λl(G;p,q)≤(2q-1)Δ(G) 6p-3。     

Zv上（y，k，k-1）-不相交差族的构造方法

给出了不相交差族的3种新构造方法：利用循环的B（k，1；v）（即CB（k，1；v））；利用循环的GDD及半循环的frame；当p≡5（mod12）为素数时，Z5p上的（5p，3，2）-DDF有一种特殊的构造方法．并得到了参数为（v，3，2）和（v，4，3）的不相交差族的一些新结果．     

判断k-可序哈密顿-连通图的新条件

具有n个顶点的图G(n≥3)是k-可序哈密顿-连通的(k是整数,且2≤k≤n),如果对于G中每一个具有k个不同顶点的可序集合S={v1v2,…,vk},都存在G中的哈密顿路P包含S且不改变其中元素的次序.本文证明了:对于具有n个顶点的图G,u、v是G中任意两个不相邻的顶点,且d(u)+d(v)≥n+1.如果G是「k+1/2﹁-连通的k-可序图,k是整数且2≤k≤n/12,则G是k-可序哈密顿-连通图.     

关于1坚韧图的最长圈

令G 是 p 阶 1坚韧图,且λ=min{d(u)+d(v))|u,v∈V(G);uv∈E},δ=min{d(u)|u∈V(G)},本文证明G的周长 c(G)=p,若 P≤2λ-2δ+2;c(G)≥2λ-2δ+2,若 p>2λ-2δ+2。对某些图来说 c(G)的下界是可以达到的。     

点可迁图的限制边连通度

对于度k( ≥ 2 )的点可迁连通图的限制边连通度λ′,已知k≤λ′≤ 2k- 2 ,且λ′的界可以达到 .在此基础上 ,对度为k的点可迁图G进一步给出了满足λ′(G) =k的两个充要条件 .接着 ,对任意的连通图G0 证明了λ′(K2 ×G0 ) =min{2δ (G0 ) ,2λ′(G0 ) ,v(G0 ) }.最后证明了对任意满足 0≤s≤k- 3的整数s,存在度为k的点可迁连通图G满足λ′(G)=k s当且仅当k为奇数或者s为偶数     

外部平面图的L(p,q)-标号

对于正整数p,q,n与图G,如果函数φ:V(G)→｛0,1,2, ,n｝满足如下关系:若distG(u,v)=1,则|φ(u)-φ(v)|≥p;若distG(u,v)=2则|φ(u)-φ(v)|≥q,那么称函数φ为图G的L(p,q) 标号.在所有L(p,q) 标号中最小的n称为(p,q) 跨度,记作λ(G;p,q).本文证明了如下结论:设图G是一个最大度为Δ的外部平面图,那么λ(G;p,q)≤qΔ+4p+2q-4.     

路和圈上的锥的D(2)-点可区别正常边染色

设G是顶点集合为V(G)=｛v0i|i=1,2,…,p｝的简单图,n是正整数, 称Mn(G)为G上的锥(或广义Mycielski图),如果 V(Mn(G))=｛v01,v02,…,v0p;v11,v12,…,v1p;…;vn1,vn2,…,vnp,w｝, E(Mn(G))=E(G)∪｛vijv(i+1)k|v0jv0k∈E(G), 1≤j, k≤p,i=0,1,…,n-1｝∪｛vnjw|1≤j≤p｝。 讨论了路和圈上的锥的D(2)-点可区别正常边染色,并给出了相应的色数。     

DTS(v)嵌入到DB(4,1;w)的研究

设(V,B)为一个DB(k,λ;v),(W,(?))为一个DB(k',λ';v')。如果V(?)W并且(?)/v=B,即B={B:B∈(?),B(?)V},我们称(V,(?))嵌入到了(W,(?))中。主要给出了当k=3,k'=4,λ=λ'=1时,DTS(v)的嵌入谱的估计。同时,确定了小阶数的DTS(v)的嵌入谱。     

蒲公英图T_m~r的k-边优美指标集

设G=(V,E)是一个p点q边图.对于非负整数k,若存在双射f:E→{k,k+1,…,k+q-1},使得其导出映射f+:V→Zp,f+(u)≡∑(u,v)∈Ef(u,v)mod p也是一个双射,则称此图G是k-边优美的.称GEI(G)={k:G是k-边优美的}是G的边优美指标集.完全确定了蒲公英图Trm(m>0,r≥0)的边优美指标集.     

关于完全3部图的色唯一性

文章设P(G,λ)是图G的色多项式,若对于任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(G≌H),则称图G是色唯一图;通过比较3部图的4色类的划分数证明,如果4≤v+2≤k≤2v,n>(k-1)2/4,则完全3部图K(n,n+v,n+k)是色唯一图。     

完全三部图K(n-k,n-v,n)的色唯一性

设P(G,λ)是图G的色多项式,如果任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(GH),则称图G是色唯一图.文献[Lau G C,Peng Y H.Chromatic uniqueness ofcertain complete tripartite graphs.Acta Mathematica Sinica,English Series,2011,27(5):919-926]中提出一个猜想(若k≥v≥2,n≥k2/4+v+1,则完全三部图K(n-k,n-v,n)是色唯一的),并证明了若2≤v≤4,k≥v≥2,n≥k2/4+v+1,则K(n-k,n-v,n)是色唯一的.通过比较三角形子图和无弦四边形子图的个数,证明了若v≥4,k≥2v2+4,n≥(k+2)2/8+3,则K(n-k,n-v,n)是色唯一图。     

Super-Edge-Connectivity of G(k,d,s)(s≥k/2)

A graph G is super-edge-connected,for short super-λ,if every minimum edge-cut consists of edges adjacent to a vertex of minimum degree.Alphabet overlap graph G(k,d,s)is undirected,simple graph with vertex set V={v|v=1()kv…v;vi∈{1,2,…,d},i=1,…,k}.Two vertices u=(u1…uk)and v=(v1…vk)are adjacent if and only if us+i=vi or vs+i=ui(i=1,…,k-s).In particular G(k,d,1)is just an undirected de Bruijn graph.In this paper,we show that the diameter of G(k,d,s)is k s,the girth is 3.Finally,we prove that G(k,d,s)(s≥k/2)is super-λ.     

高度平面图的列表L(p,q)-标号

如果平面图G的最大度Δ(G)=|V(G)|-k, k=1,2,…,则称G为一个hk-图,k=1,2的hk-图称为高度平面图.研究了高度平面图G的列表L(p,q)-标号问题, 给出了高度平面图G的列表L(p,q)-标号数λl(G;p,q)的上界,并对h1-图证明了λl(G;p,q)≤(2q-1)Δ 6(p-q);对h2-图有λl(G;p,q)≤(2q-1)Δ 8p-6q-1.     

Corona图P_nｏF_(1,m)、C_nｏC_m与C_nｏF_(1,m)的b-染色数

在图G=(V,E)的一个正常染色{V_1,V_2,…,V_k}中,若i,j,1≤i≠j≤k,■u∈V_i,v∈V_j,使得uv∈E,称该染色为b-染色.令b(G)=max{k|V_1,V_2,…,V_k:i,j,1≤i≠j≤k,■u∈V_i,v∈V_j,uv∈E},称b(G)为图G的b-染色数.一个图G是b-连续的,如果k:χ(G)≤k≤b(G),用k种颜色可实现对G进行b-染色.通过构造特殊染色方案,研究了Corona图P_noF_(1,m)、C_noC_m与CnoF_(1,m)的b-染色数与b-连续性.