n-可扩图的局部邻域条件娄定俊

设G是阶为v的图且具有完美对集。设n是正整数,满足n≤(v-2)/2.G称为n-可扩的,是说:G中任意n条独立边包含在G的一个完美对集中。 设G是一个图且v∈V(G)。定义N_k(v)={u|u∈V(G)且d(u,v)=k}。设u,v∈V(G)满足d(u,v)=2.记I(u,v)=|N(u)∩N(v)|。定义散度α~*(u,v)如下: n_(u+v)(W)=max{|S||w∈N(u)∩N(v),S是G[{w}∪N_G(w)]中包含u和v的独立集},     

关于两类图的整和数

本文中的图均指无向简单图,以N,Z分别表示全体自然数及全体整数集合.对子集S(?)Z(N),S上的整和(和)图定义为图G=(S,E),满足条件对u,v∈S,uv∈E当且仅当u v∈s.此时,S称为G的一个整和(和)标号.一个图称为整和(和)图,如果它同构于某一子集S(?)Z(N)上的整和(和)图.容易验证,对一个有m条边的n阶图G,G∪mK_1是一个和图,只需标定G的顶点为2~i,1≤i≤n,同时对v_i,v_j∈E(G),标定对应的孤立点2~i 2~j即可.因此,对每一个图G,存在一个最小的非负整数r,使G∪rK_1为和图,记σ(G)=r,并称为G的和数.图的整和数ξ(G)类似定义,只是标号范围放宽到整数集上.容易看到ξ(G)≤σ(G).     

图的连通度与Hamilton连通性

一、引言 我们讨论的图均为简单图,K和α分别表示图的连通度和独立数。我们采用文献[1]的术语和符号,并记G_n~k={G丨G为n阶k-连通图},H_e={G丨G是Hamilton连通图},用P_H(u,v)表示从u到v的Hamilton路。图G中的路P称为控制路,如果G[P(G)\V(P)]均为孤立点.给出图G中的一条(x,y)-路P,总认为是从x到y定向,表示的反向。若u,v∈V(P),则uv表示P上沿从u到v的路。又u≠y,v≠x,则u~+和v~-分     

无向循环图的同构

设n>1是整数,N={1,2,…,n-1),K={K_1,…K_m}■N。按如下方法定义一个有向循环图G_n(K):点集V={v_0,v_1,…,v_(n-1)},边集E={v_iv_j|存在自然数i,1≤t≤m,使得j-i≡K_t(mod n)}。     

氮化硅纳米粒子的量子限制效应

G是一个连通图,SV(G)和u∈V(G),我们记 N(S)={v∈V(G)\S:存在w∈S使得vw∈E(G)}, N(u)={v∈V(G):uv∈E(G)},分别称为S和u点在G中的邻域.进一步,N(u)=N(u)∪{u},u点的闭邻域,和 G(u)=G[N(u)]     

t可约m×n 二部分竞赛图的得分表偶

设(X,Y)是m×n 二部分竞赛图T_(m,n)的顶点集合V(T_(m,n))的有序分划,其中X=(x_1,x_2,…,x_m},Y={y_1,y_2,…,y_n},x_i、y_j 在T_(m,n)中的得分分别为a_i、b_j,l≤i≤m,l≤j≤(?),且a_1≤a_2≤…≤a_m,b_1≤b_2≤…≤b_n.记A=(a_1,a_2,…,a_m),B=(b_1,b_2,…,b_n),则T_(m,n)     

一类图集的Ramsey数

在图G的一个顶点v上加一条端线e=vw,w(?)V(G),称为G的一次发芽。由图G分别在它的每个顶点处一次发芽而得到的图集,称为G的一次发芽集,记为(G)_1。图集(?)中所有图的一次发芽集的并集,称为(?)的一次发芽集,记为(?)_1。图G的2次发芽集(G)_2可由(G)_2=((C)_1)_1定义。一般,C的n次发芽集(G)_n可递归地定义为     

符号空间中子位移的测度熵与维数

1 定义与结论随着分形几何和动力系统的深入发展,符号动力学已成为研究浑沌和分形的一个有力工具,进一步讨论符号空间的有关分形特征是有用的.本文将给出符号空间中子位移的测度熵与维数的关系,证明Bowen的维数公式在非Markov结构下成立,从而得到关于维数的不变原理.设E={1,…,N},其中N≥2,赋与E以离散拓扑,设积空间∑_N=∏_i~∞=_1E,称∑_N为 n个符号组成的符号空间,它是一个紧致的可度量化空间.设P=(P_1,P_2,…,P_N)满足0相似文献   

冠C_(2n)☉K_1协调猜想的证明

一个图G=(V,E)称为是协调的(harmonious),如果存在一个单射h:V(G)→Z_q,其中Z_q={0,1,……,q-1},q=|E(G)|,由此导出的边标号h~*(u,v)=h(u)+h(v)(modq)是1-1的。若G是树,则允许有且仅有两点的标号相同,这时h称为G的一个协调标号。若上述映射导出     

Levin猜想之证明

一、若干记号 设B={0,1},N={0,1,2,…}.B~n(n∈(N)和B~∞分别表示字母表B上的长为n的字全体和右端无穷的字全体。记B~*=(?)B~n。用x表示有限或无限0-1串,即x∈B~*∪ B~∞,l(x)表示x的长度,带有下标的x_i(i=1,2,…)表示B中的字母,x表示取值于B的随机     

具有最多边的唯一因子图

§1.引言 设G=(V,E)是简单图,V和E分别是G的顶点集和边集。n=|V|称为顶点数,m=|E|称为边数。设S(?)V,从G中去掉S得到的子图,用G-S表示,就是V-S生成的子图。 G的两条边e_1,e_2若有一个公共端点,称为是关联的.设F(?)E是G的边子集,F中任     

关于 L(S)的一点结果

设A_(m×n)是行和为R=(r_1,r_2,…,r_m)、列和为Q=(q_1,q_2 …,q_n)的(0,1)矩阵。设δ_i=(1,…,1,0,…,0),其中前r_i个位置为1,其余为0,A_(m×n)=称为A_(m×n)的极左矩阵,记其列和向量为S.设L(S)={S|SS,S的分量递降且为非负整数}。若S、TεL(S),S≠T,ST,且不存在V L(S),V≠S,V≠T,满足SVT,则称S是T的直接后继。设S=(S_1,S_2,…,S_n),T=(t_1,t_2,…,t_n),我们有定理1 若S是T的直接后继,则存在i、j’满足S_i+1=t_i,S_j-l=t_j,S_k=t_k(1≤k≤n,     

关于多重共轭Fourier积分的Riesz球平均

设E_k为k维欧氏空间(k≥2),Q_k={x∈E_k,-π≤x_i≤π≤,i=1,2,…,k}。B(x_0,r)={x∈E_k,|x-x_0|≤r},Ω={x∈E_k,|x|=1},P(x)为n次     

大次和的1-坚韧图中的最长圈

给定一个图G,以‘(G)表示G的周长,并记一(。卜Mi·{客“(一):‘一,ng一Li的结果:设G是”阶2一连通图,若厅(G))n李3.则G是哈密尔顿图. 推论2设G‘留;,若生(3,一23)2,》15奇数;1一2r|l!|||夕、||||书纷we A\是G的无关集a3(G)(3,一16),》16偶数;·3(。卜Mi·{客己(一卜!愈N(一,!”(14。:,。2,,3}是G的无关集则G是哈密尔顿图. 该推论改进了G〔罗1,若内(G)Fa夕bender的结果:设、。)一Mi·{{(知一14),(,)1一2李|训州日N(,‘:{,,,,2,。丹是G的无关集·、(‘卜Mi·{{立N(一)卜{一提使自N(。)铃价的无关集13),则G是哈密尔顿图. 推论3.设G…     

一个k-Hamilton-良好的序列

设G是一个无向简单图,t是一个正整数。令(?)_t(G)={Y(?)V(G)|Y是G的独立集,|Y|=t}。对于Y∈(?)_t(G),i∈{0,1,2,…,t},令S_i(Y)={v∈V(G)||N(v)∩Y|=i},s_i(Y)=|S_i(Y)|。1990年,陈冠涛等(私人通信)引入了如下概念。     

愉快图的Bodendiek猜想之证明

一个简单图称为愉快的,如果存在用集合S={0,1,2,…,ε}(其中ε=ε(G)是G的边数)中不同整数的顶点标号ι,使得如下定义的诱导边标号ι′对每条边uv都有不同的标号:     

比赛图的得分向量

设T_n表示n比赛图,依照L.Lovász,如果T_n.中任意n 1-k个顶点诱导的子比赛图都具有性质P,则T_n称为k-P的,这里P表示比赛图的不变性质,比如强性,可约性,等等。如果T_n是k-P的,但不是(k 1)-P的,则T_n称为严格k-P的。特别,1-P T_n等价于P的。严格1-P T_n简称为严格P的。设R=(r_1,r_2,…,r_n)是T_n的得分向量,     

■样条的Budan-Fourier定理及其应用

设n 1次多项式(n≥0)P_n 1(x)=a_0 a_1x … a_nx~n x~(n 1)的所有零点都是实的,零点的集合记为T={t_0,t_1,…,t_n},相应地有微分算子     

代数数域上的加型方程

1.引言 命K为一个n次代数数域。命K~(1),…,K~(n)表示K的n个共轭域,K~(i)(1≤i≤r_1)为实域而K~(i),K~(i r_2)(r_1 1≤i≤r_2 r_2)为共轭覆域,此处r_1 2r_2=n。对于r∈K,我们用r~(i)(1≤i≤n)表示r的共轭数。命r_i(1≤i≤n)为K的数及x_i(1≤     

包装(P,P—1)(P,P)图对和Slater问题

设G是简单无向图。V(G),E(G)分别表示G的顶点集和边集。如果|E(G)|=|V(G)|-K,则称G是(P,P—K)图。对于同阶图对{G_1,G_2},如果G_1与的某个子图同构,则称图对{G_1,G_2}是可包装