边着色路到完全图的嵌入

一、一个猜想设 P_n 为具有 n 个顶点的一条路,它的 n-1条边着上了不同的颜色,若这个着色能扩充为 n 个顶点的完全图 K_n 的一个正常的 x′(K_n)一边着色,则称边着色路 P_n 能嵌入于完全图.一般说来,设 G 是具有边色数 x′(G)的一个简单图,令 M(G)为 G 中所有满足以下性质的子图 H(?)G 的集合:存在 G 的一种正常的 x′(G)-边着色使得 H 的各条边具有不同的颜色.设 K_n 是 n 个顶点的完全图,把集合 M(K_n)简记为 M_n 于是我们一开始提出的问题“P_n 能否嵌入于完全图”等价于“P_n 是否属于 M_n”.     

星样树与路的笛卡尔积图的任意可分性（英文）

一个图G称为是任意可分的(简记AP),如果对于正整数|V(G)|的任一满足∑_(i=1)~pn_i=|V(G)|的划分τ=(n_1,n_2,…,n_p),总是存在顶点集V的一个划分(V_1,V_2,…,V_p)满足|V_i|=n_i,i=1,2,…,p,使得每个V_i导出的图是图G的一个连通子图.记S(a_1,a_2,…,a_t,b_1,b_2,…,b_l)是最大度△(S)=t+l的星样树,其中a_i是奇数,b_j是偶数且a_1≤a_2≤…≤a_t,b_1≤b_2≤…≤b_l.我们证明了对于一个大于等于2的偶数n,当△(S)≤n+1时,如果t≤2,或t≥3且a_3 1,则笛卡尔积图S□P_n是AP的.对于一个大于2的奇数n,如果△(S)≤n+1且t≤2,则S□P_n是AP的;如果△(S)≤n+1且t≥3,则S□P_n不是AP的.     

关于图的连通DOMINATION的若干结果

设G是n阶连通图.γ_c(G),d_c(G),i(G)和ir(G)分别表示G图的连通Domination数,连通Domatic数,独立Domination数和Irredundance数,k(G)表示G的连通度.本文证明了下列结论. (1) 如n≥3,则i(G) γ_c(G)≤n [n/3]-2; (2) γ_c(G)≤4ir(G)-2; (3) γ_c(G)≤k(G) 1; (4) 如G≠K_n,则d_c(G)≤k(G). 此外,本文给出了满足等式γ_c(G) γ_c(G)=n和γ_c(G) γ_c(G)=n 1的图G的一个特征.     

Kronecker乘积图的超连通性(英文)

设G1和G2是两个连通图,则G1和G2的Kronecker积G1×G2定义如下:V(G1×G2)=V(G1)×V(G2),E(G1×G2)={(u1,v1)(u2,v2):u1u2∈E(G1),v1v2∈E(G2)}.我们证明了G×Kn(n≥4)超连通图当且仅当κ(G)n>δ(G)(n 1),其中G是任意的连通图,Kn是n阶完全图.进一步我们证明了对任意阶至少为3的连通图G,如果κ(G)=δ(G),则G×Kn(n≥3)超连通图.这个结果加强了郭利涛等人的结果.     

可圈的一个充分条件

本文我们证明如下结果:设G=(V,E)是一个n(n≥3)阶k-连通(k≥2)图,记X1,X2,…,Xk为V的子集,X=X1∪X2∪…∪Xk.若对每个I,I=1,2,…,k,满足:对任意的u,v∈Xi,有d(u) d(v)≥n或|N(u)∪N(v)|≥n-δ或|N(u)∩N(v)|≥α,这里δ是G的最小度,α是G的独立数,则G是X-可圈的.     

Hamilton连通性和邻域并条件

设G＝（V，E）为简单图，δ为图G的最小度，1987年Faudree等人给出NC＝min{|N(x)∪N(y)‖x,y∈V(G),xy∈N(G)}，有关文献曾研究3连通的H连通图，本文进一步得到：若G是n阶2连通图，且NC≥n-δ，则G除几个图外均是H连通图，从而，完成了邻并条件的H连通图问题。     

哈密尔顿性和部分平方图的独立集

设G是一个图,G的部分平方图G*满足V(G*)=V(G),E(G*)=E(G)∪{uv:uv■E(G),且J(u,v)≠■},这里J(u,v)={w∈N(u)∩N(v):N(w)■N[u]∪N[v]}.利用插点方法,证明了如下结果:设G是k-连通图(k2),b是整数,0min {k,(2b-1+k)/2}(n(Y)-1),则G是哈密尔顿图.同时给出图是1-哈密尔顿的和哈密尔顿连通的相关结果.     

邻域并与泛圈图

本文中 ,我们用邻域并对泛圈图进行深入的研究 ,主要取得了“2连通 n( n≥ 3 )阶图 G,满足下列条件之一 ,则 G是泛圈图 : :δ≤ ( n-7) /3 ,N C≥ ( 2 n-3 ) /3 ; :( n-6) /3≤ δ≤ ( n+2 ) /3 ,N C≥ 2 n/3 ; :δ≥ ( n+3 ) /3 ,N C≥ ( 2 n-3 ) /3 .当 3≤ n≤ 14时 ,N C≥ 2 n/3”     

独立集的度和与图的哈密尔顿性

关于哈密尔顿连通图的一个基本结果是Ore给出的：设G是n阶图,若对于任意两个不相邻顶点u和v,有d(u) d(v)≥n 1,则G是哈密尔顿连通的．设G是一个图,对于任意u (?)V(G),令N(U)=∪_(u∈∪)N(u),d(U)=|N(U)|,称d(U)是U的度．本文利用独立集的度和得到如下结果：设s和t是正整数,G是(2s 2t 1)-连通n阶图．若对于任两个强不交独立集S,T,|S|=s,|T|=t,有d(S) d(T)≥n 1．则G是哈密尔顿连通的．同时也得到图的哈密尔顿性的其它相关结果．两个独立集S和T称为强不交的,如果S∪T也是独立集．     

单圈图的代数连通度的排序

n阶图G称为是一个单圈图,如果G是连通的,并且G的边数也是n.用U(n)表示所有n阶单圈图所成的集合.给出了当阶数n≥25时,代数连通度为前九大的n阶单圈图及它们的代数连通度.     

随机图的广义3-连通度

图的广义连通度的概念是由Chartrand等人引入的.令S表示图G的一个非空顶点集,κ(S)表示图G中连结S的内部不交树的最大数目.那么,对任意一个满足2≤r≤n的整数r,定义G的广义r-连通度为所有κ(S)中的最小值,其中S取遍G的顶点集合的r-元子集.显然,κ_2(G)=κ(G),即为图G的顶点连通度.所以广义连通度是经典连通度的一个自然推广.本文研究了随机图的广义3-连通度,证明了对任一给定的整数k,k≥1,p=(log n+(k+1)log long n-log lon logn)/n是关于性质κ_3(G(n,p))≥k的紧阈值函数.我们得到的结果可以看作是Bollobas和Thomason给出的关于经典连通度结果的推广.     

n 阶临界3-边连通图的最大边数

本文中未经说明的术语和记号采自[2].设 G=(V,E)是一个简单图。G 的顶点数记作 n(G),边数记作 m(G),即 n(G)=|V|,m(G)=|E|.假设 G 是3-边连通图.G 的顶点 v(?)V 称为 G 的临界点,如果 G-v 不是3-边连通的;否则称为 G 的非临界点.如果每个 v(?)V 都是 G 临界点,则称 G 是临界3-边连通图.临界3-边连通图类记作 A,A_n 是 A 中所有 n 阶图的集合.假设 G(?)A,则对每个 v∈A,     

Fourier级数及其导级数的逼近

设p_m≥0↓,sum from k=0 to n(p_n)=P_m,n=0,l,…,p_0=P_0=1,P_n→∞(n→∞)若N_n=1/P_n sum from k=0 ton(p_(n,k)S_k→S(n t。0→∞)),则说{S_k}关于算子(N,p_n)收敛于S.设f(x)∈L_(?),S_n(f,x)为     

无爪3 -正则图的独立数

如果图G的一个集合X中任两个点不相邻, 则称 X 为独立集合. 如果 N[X]=V(G), 则称X是一个控制集合. i(G)(β(G))分别表示所有极大独立集合的最小(最大)基数. γ(G)(Γ(G))表示所有极小控制集合的最小(最大)基数. 在这篇论文中, 作者证明如下结论: (1) 如果 G ∈R 且G 是n阶3 -正则图, 则 γ(G)= i(G), β(G)=n/3. (2) 每个n阶连通无爪3 -正则图 G, 如果 G(G≠ K₄) 且不含诱导子图K₄-e, 则 β(G) =n/3.     

连通图的谱半径上界

图谱理论是图论研究的重要的领域之一.设图G是n阶简单连通图,具有n顶点和m条边的连通图,p(G)为图G的邻接矩阵的谱半径.利用代数的方法得出两个ρ(G)的上界为:■与■和达到上界的图.     

(n,k)-排列图的条件连通度(英文)

点连通度是衡量互联网络容错性的一个重要参数.尽管点连通度能正确地反映了系统的容错性能,但是不能正确反映大规模网络的健壮性能.条件连通度通过对各分支附加一些要求(当整个网络被破坏时)来克服这个缺点.给定一个基于图G的网络和一个正整数l,G的R~l-连通度,记为k~l(G),定义为图G的最小节点子集的节点数,使其去掉后,G是不连通的,且每个分支的最小度至少是l.在本文中,我们得到了(n,k)-排列图的条件连通度k~l(A(_n,k))=[(l+1)k-l](n-k)-l,其中k≥l+2,n≥k+l.     

k连通图可缩边导出子图的连通性

引进S1 3边形的概念 .证明了 ,对于k(k =3或 4)连通图G ,若G无S1 3边形 ,则 是 2连通的 ;另外也得到 ,设G是k(k≥ 2 )连通图 ,若对G的任一断片F ,有｜F｜ >[k/2 ]+ 1 ,则 是 2连通的 .从而改进并推广了N .Dean的结论 .     

连通图中过指定顶点集的圈的存在性

图论中的一个重要问题是Hamilton圈的存在性问题.由于一般的Hamilton图的充要条件难于获得,故一些作者便退一步在某些给定类型的图中寻求长度尽可能大的圈.例如,Dirac即证明了2-连通图中存在着经过某一指定顶点集N(u)UN(v)U{u,v}的圈,从而得到了如下的定理(可参看[3]的介绍): 定理A.设G是个n阶的2-连通图,P是G中的一条最长路,u及v是P的两端点,d(u)+d(v)=f.若4≤f相似文献   

超级限制边连通二部图的充分条件

设S是连通图G的一个边割.若G-S不包含孤立点,则称S是G的一个限制边割.图G的最小限制边割的边数称为G的限制边连通度,记为λ'(G).如果图G的限制边连通度等于其最小边度,则称图G是最优限制边连通的,简称λ'-最优的.进一步,如果图G的每个最小限制边割恰好分离出图G的一条边,则称图G是超级限制边连通的,简称超级-λ'的.设G是一个最小度δ(G)≥2的n≥4阶二部图,ξ(G)是G的最小边度.本文证明了(a)若ξ(G)≥(n/2-2)(1+1/δ(G)-1),则G是λ'-最优的;(b)若ξ(G)>(n/2-2)(1+1/δ(G)-1),则G是超级-λ'的,除非图G是K2,n-2,n≥6或是Cartesian积图Kn/4,n/4×K2,其中n≥8且n整除4.最后,论文举例说明该结果是最好可能的.     

半群P_n(k)的正则性和Green关系

设P_n是X_n={1,…,n}上的部分变换半群.对任意1≤k≤n,令P_n(k)={α∈P_n:(x∈dom(α)x≤k■xα≤k},则易验证P_n(k)是P_n的子半群.刻画了半群P_n(k)的正则元的特征,并且描述了这个半群上的Green关系.