半CAP-子群与有限群的性质

设G是有限群,G的子群H称为G的半CAP-子群,如果存在G的一个主群列1 =G0△←G1 …△←Gn-1△←Gn=G使得H覆盖或者避开Gi/Gi-1,其中i=1,2,…,n.本文主要讨论极小子群和4阶循环子群的半覆盖-避开性对有限群结构的影响.     

若干n重积图的点可区别边色数

通过研究若干n重积图的边色数及点可区别边色数,就可证明■(Gi)=△(Gi),i=1,2,L,n,则∑=′×××=■△(G_i)其中G1×G2×L×Gn为G1,G2,L,Gn的n重积图.     

顶点最大度被限制的图的边转发指数

对于给定的n阶连通图G,一个路由选择R是指G中的n(n-1)条路集,其中每个有序点对都有路集中的一条路连接.图G关于R的边转发指数π(G,R)是R中路经过一条边的最大条数.图G的边转发指数π(G)是G关于任何路由选择R的边转发指数π(G,R)的最小值.符号πΔ,n表示所有顶点数为n,最大度至多为△的图中最小边转发指数.当n≥4p 1,且n()[4p [1/3(2p-1)]-1,6p]时,其中p≥1,确定了πn-2p,n的值.     

图中具有指定性质的独立4-圈

主要给出了图G恰好含有s个K3和k-s个K4的最小度条件即:设G是一个简单图,s,k是两个正整数且s k,其中G的顶点个数n≥3s+4(k-s)+3,如果G中任意两个不相邻顶点的最小度之和σ2(G)≥4n-3s-8/|2|或者最小度δ(G)≥3n+2k-s-2/4,则G包含k个顶点不相交的圈C1,C2…Ck,并且Ci=K3其中1≤i≤s,Cj=K4其中sj≤k.     

6长圈带2条悬边的8阶连通图的图设计

构造了所需的带洞图设计, 再结合一些小阶数的图设计的存在性, 得到了关于图Gi (i=1,2,3,4)的图设计(v, Gi ,1)-GD的存在谱, 其中图Gi (i=1,2,3,4)是给6长圈增加2条悬挂边所得的8阶连通图, 且G1, G2, G3, G4互不同构.     

双星图的Ramsey数的上界

对给定的两个图G和H,Ramsey数R(G,H)是最小的正整数N,使得对完全图KN的边任意红/蓝着色,则或者存在红色子图G,或者存在蓝色子图H.双星B(m,n)为直径是3,有两个中心顶点,其顶点度分别为m+1和n+1的树.得到,当nm时,R(B(m,n))2n+m+2;当n=m或n=m+1时,R(B(m,n))=2 m+n+2.     

3正则3连通图的转发指数

n阶连通图G的路由选择R是由连接G的每个有向顶点对的n(n-1)条路组成.R经过G的每个顶点(每条边)的路的最大条数称为G关于R的点转发指数ξ(G,R)(边转发指数π(G,R)).对G的所有路由选择R,ξ(G,R)(π(G,R))的最小值称为G的点转发指数ξ(G)(边转发指数π(G)).对于k正则k连通图G, Fernandez de la Vega和Manoussakis [Discrete Applied Mathematics, 1989, 23(2):103-123]证明ξ(G)≤(n-1)·[(n-k-1)/k]和π(G)≤n[(n-k-1)/k],并且猜想ξ(G)≤[(n-k)(n-k-1)/k].我们分别改进了ξ(G)≤(n-1)[(n-k-1)/k]-(n-k-1)和π(G)≤n[(n-k-1)/k]-(n-k),并且证明了猜想对k=3的情形.     

图的2-距离着色

简单图G(V,E)的2-距离着色是正常的顶点着色且距离不大于2的任意两个顶点着不同的颜色,给出了网格的2-距离色散,并通过运用线图构造了一类特殊图,从而证明了最大度为△的图G的二距离色数的界为16/5△2+8/3△+16/5≤x2d(G)≤min{△2+1,n}     

若干多重联图的边染色

设G1,G2,…,Gn是n个(n≥2)两两不相交的简单图,它们的n-重联图是在G1 G2 … Gn中,将Gi的每一顶点与Gj的每一顶点连接起来(i≠j,i,j=1,2,…,n)所得到的图,简记为K(G1,G2,…,Gn).若Gi≌G,i=1,2,…,n,则称K(G1,G2,…,Gn)为G的等n-重联图,简记为K(n,G).本文研究了若干多重联图的边染色.     

若干积图的点可区别边染色

证明了:(1)两个n(n2)阶完全图的积图的点可区别边色数为2n. (2)对阶至少是3的完全图Kn,若χ′vd(G)=Δ(G),则χ′vd(G×Kn)=n+Δ(G).(3)若χ′vd(Gi)=Δ(Gi),i=1,2,则χ′vd(G1×G2)=Δ(G1)+Δ(G2).