λKv的最大K2,3填充设计和最小K2,3覆盖设计

对于一个有限简单图G,λKv的G-设计(G-填充,G-覆盖),记为(v,G,λ)-GD((v,G,λ)-PD,(v,G,λ)-CD),是一个(X,B),其中X是Kb的顶点集,B是Kv的子图族,每个子图(称为区组)均同构于G,且Kv中任一边都恰好(最多,至少)出现在B的λ个区组中.一个填充(覆盖)设计称为是最大(最小)的,如果没有其它的这种填充(覆盖)设计具有更多(更少)的区组.本文对于λ>1确定了(v,K2,3,λ)-GD的存在谱,并对任意λ构造了λKv的最大K2,3-填充设计和最小K2,3-覆盖设计.     

一类图设计的构造

设Kv是一个v点完全图,G是一个有限简单图,Kv上的一个图设计G-GD(v)是一个对子(X,B),其中X是Kv的顶点集合,B是Kv的一些与G同构的子图(称为区组)的集合,使得Kv的任意一条边恰出现在B的一个区组中．文中讨论的简单图是C(r)10,即带有一条弦的10长圈(含有11条边),其中r表示弦的两个端点之间的顶点个数,1≤r≤4．给出了C^（r）10-GD(v)的存在谱：v=0,1(mod11)且v≥11．     

六点七边图的λ-填充与λ-覆盖

λKv为λ重v点完全图,G为有限简单图.λKv的一个G-设计(G-填充设计,G-覆盖设计),记为(v,G,λ)-GD((v,G,λ)-PD,(v,G,λ)-CD),是指一个序偶(X,B),其中X为Kv的顶点集,B为Kv中同构于G的子图的集合,称为区组集,使得Kv中每条边恰好(至多,至少)出现在B的λ个区组中.一个填充(覆盖)设计称为最大(最小)的,如果没有其它的填充(覆盖)设计有更多(更少)的区组.本文中,我们构作了三个六点七边图的最大填充与最小覆盖.     

λKv的最大K2,3填充设计和最小K2,3覆盖设计

对于一个有限简单图G,λK_v的G-设计(G-填充,G-覆盖),记为(v,G,λ)-GD((v,G,λ)-PD,(v,G,λ)-CD),是一个(X,B),其中X是K_v的顶点集,B是K_v的子图族,每个子图(称为区组)均同构于G,且K_v中任一边都恰好(最多,至少)出现在B的λ个区组中.一个填充(覆盖)设计称为是最大(最小)的,如果没有其它的这种填充(覆盖)设计具有更多(更少)的区组.本文对于λ>1确定了(v,K_2,3,λ)-GD的存在谱,并对任意λ构造了λK_v的最大K_2,3-填充设计和最小K_2,3-覆盖设计.     

偶长圈加一条弦的分拆

设Kv是一个v点完全图.G是一个有限简单图.Kv上的一个图设计G-GD是一个对子（X,B）,其中X是Kv的顶点集合,B是Kv的一些与G同构的子图（称为区组）的集合,使得Kv的任意一条边恰出现在B的一个区组中.文中讨论的简单图是C^（r）2k,即带有一条弦的2k长圈,其中r表示弦的两个端点之间的顶点个数,1≤r≤k-1.文中给出了一个构作C^（r）m设计的统一方法,并得到关于v≡0,1（mod2k＋1）时C^（r）2k-GD（v）的一系列结果.     

完全二部图的Kp,p-分解大集的存在谱北大核心CSCD

令H,G是两个简单图,G是H的一个子图.H的G-分解,记为（λH,G）-GD,是指将图λH的所有边分拆为若干个与G同构的子图（称为G-区组）.H的G-分解的大集,记为（λH,G）-LGD,是指图H的所有与G同构的子图的一个分拆Β1,Β2,…,Βm,使得每个Bj（1≤j≤m）为一个（λH,G）-GD （称为小集）.本文中,我们对完全二部图的K（p,p）-分解的大集进行了研究,利用Kv的λ重Kκ-因子大集的存在性结果,采用直接构造的方法,得到了大集（λK（m,n）,K（p,p））-LGD的存在谱,其中p为任意素数.     

完备图分拆为带一条弦的(2k-1)-长圈

本文给出了构造G-设计的一个统一方法及当v≡1(mod 4k)时的C_(2k-1)~((r))-GD(v)的存在性,其中C_(10)~((r)),1≤r≤k-2表示带一条弦的2k-1长圈,r表示弦两个端点间的顶点个数。     

一类完全三部图的K1,3-因子大集

令G是一个有限图,H是G的一个子图.若V(H)=V(G),则称H为G的生成子图.图G的一个λ重F-因子,记为Sλ(F,G),是G的一个生成子图且可分拆为若干与F同构的子图(称为F-区组)的并,使得V(G)中的每一个顶点恰出现在λ个F-区组中.一个图G的λ重F-因子大集,记为LSλ(F G),是G中所有与F同构的子图的一个分拆{B_i}_i,使得每个B_i均构成一个Sλ(F,G).当λ=1时,λ可省略不写.本文中,我们证明了当v≡4 mod 24时,存在LS(K1,3,Kv,v,v).     

完全二部图的K_(p,p)-分解大集的存在谱

令H,G是两个简单图,G是H的一个子图.H的G-分解,记为(λH,G)-GD,是指将图λH的所有边分拆为若干个与G同构的子图(称为G-区组).H的G-分解的大集,记为(λH,G)-LGD,是指图H的所有与G同构的子图的一个分拆Β_1,Β_2,…,Β_m,使得每个B_j(1≤j≤m)为一个(λH,G)-GD (称为小集).本文中,我们对完全二部图的K_(p,p)-分解的大集进行了研究,利用K_v的λ重K_κ-因子大集的存在性结果,采用直接构造的方法,得到了大集(λK_(m,n),K_(p,p))-LGD的存在谱,其中p为任意素数.     

K2,3的多重多部图设计的构造

λKn(t)是一个λ重完全多部图,G为一个不带孤立点的简单图.所谓的图设计G-HDλ(tn)是一个序偶(X,B),其中X是Kn(t)的顶点集,B为λKn(t)的一些子图(亦称为区组)构成的集合,使得任一区组均与图G同构,且λKn(t)的任意2个不同点组成的边恰在B的λ个区组中出现.本文讨论了G=K2,3的完全多部图设计存在性问题,证明了存在G-HDλ(tn)当且仅当λn(n-1)t2≡0(mod12),n≥2,nt≥5且(n,,λt)≠(9,1,1),(12,1,1),(3,1,2),(4,1,2).     

Hamilton连通图的一个充分条件

Let G be a3-connected graph with n vertices.The paper proves that if for each pair of verti-ces u and v of G,d(u,v)=2,has|N(u)∩N(v)|≤α（αis the minimum independent set num-ber),and then max{d(u),d(v)|≥n 1/2,then G is a Hamilton connected graph.     

平面图的k-重(2k+2)-染色

G=(V,E)表示一个顶点集为V,边集为E的有限简单无向图.若存在映射φ:V(G)→Zk(n)(Zk(n)是由{1,2,…,n}的所有k-元子集构成的集合),满足:(A) uv∈E(G),有φ(u)∩φ(u)=θ,则称φ是G的一个k-重n-顶点染色.本文证明了奇围长至少为5k-7(k=4)或5k-9(k=6)的平面图G...     

哈密顿线图的一个新结果

设G是一个简单图,G1∈G,G1在G中的度定义为d（G1）=∑v∈V（G）d（v）,其中d（v）为v在G中的度数．主要结果是：设G是n≥3阶几乎无桥的简单连通图,且G≠K（1,n-1）、Q1和Q2,若对G中任何同构于四个顶点路的导出子图I,有d（I）≥2n-6,则G有一个D-闭迹,从而G的线图L（G）是哈密顿图．     

K3-free图的线图的哈密顿性

设G是一个简单图，Gi G，G1在G中的度定义为d（Gt）=∑v∈v（c）d（v），其中d（v）为v在G中的度数。本文的主要结果是：设G是n≥2阶几乎无桥的简单连通K3-free图，且G≌k1,n-1、Q1和Q2，若对G中任何同构于四个顶点路的导出子图I有d（I）≥n＋2，则G有一个D-闭迹，从而G的线图L（G）是哈密顿图。     

图的下测地数和上测地数

对于图G(或有向图D)内的任意两点u和v,u—v测地线是指在u和v之间(或从u到v)的最短路．I(u,v)表示位于u—v测地线上所有点的集合,对于S(?)V(G)(或V(D)),I(S)表示所有I(u,v)的并,这里u,v∈S．G(或D)的测地数g(G)(或g(D))是使I(S)=V(G)(或I(S)=V(D))的点集S的最小基数．G的下测地数g~-(G)=min{g(D)：D是G的定向图},G的上测地数g~ (G)=max{g(D)：D是G的定向图}．对于u∈V(G)和v∈V(H),G_u H_v表示在u和v之间加一条边所得的图．本文主要研究图G_u H_v的测地数和上(下)测地数．     

点度与图的上可嵌入性

本文证明了:(1) 设G是2-连通简单图,且不含K_3,若对任意一对距离为2的点u,u,有max{d(u),d(u)}>n/3-1,其中n=|V(G)|,则G是上可嵌入的,且条件中不等式的界"n/3-1"是不可达的;(2) 设G是3-连通简单图,若对任意依次相邻的三点u,u,W,有max{d(u),d(u),d(w)}≥n/6+1,其中n=|V(G)|,则G是上可嵌入的,且条件中不等式的界"n/6+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时也是边幻图.     

P_(4k-1)-factorization of complete bipartite graphs

Let Km,n be a complete bipartite graph with two partite sets having m and n vertices, respectively. A Pv-factorization of Km,n is a set of edge-disjoint pv-factors of Km,n which partition the set of edges of Km,n. When v is an even number, Wang and Ushio gave a necessary and sufficient condition for the existence of Pv-factorization of Km,n.When v is an odd number, Ushio in 1993 proposed a conjecture. However, up to now we only know that Ushio Conjecture is true for v = 3. In this paper we will show that Ushio Conjecture is true when v = 4k - 1. That is, we shall prove that a necessary and sufficient condition for the existence of a P4k-1-factorization of Km,n is (1) (2k - 1)m ≤ 2kn, (2) (2k -1)n≤2km, (3) m n ≡ 0 (mod 4k - 1), (4) (4k -1)mn/[2(2k -1)(m n)] is an integer.     

Vertex-distinguishing E-total Coloring of Complete Bipartite Graph K_(7,n) when 7≤n≤95

Let G be a simple graph. A total coloring f of G is called an E-total coloring if no two adjacent vertices of G receive the same color, and no edge of G receives the same color as one of its endpoints. For an E-total coloring f of a graph G and any vertex x of G, let C(x) denote the set of colors of vertex x and of the edges incident with x, we call C(x) the color set of x. If C(u)≠ C(v) for any two different vertices u and v of V(G), then we say that f is a vertex-distinguishing E-total coloring of G or a VDET coloring of G for short. The minimum number of colors required for a VDET coloring of G is denoted by χ_(vt)~e(G) and is called the VDET chromatic number of G. The VDET coloring of complete bipartite graph K_(7,n)(7 ≤ n ≤ 95) is discussed in this paper and the VDET chromatic number of K_(7,n)(7 ≤ n ≤ 95) has been obtained.