度序列已给定的部分标定图的重构问题

设G=(V,E)是简单、无向的p阶部分标定图,V={v_1…,v_p},p≥3。设u,v∈V,X,Y(?)V。记N_Y(v)为顶点v在Y中的邻集,d_Y(v)=|N_Y(v)|为v关于Y的度,为v关于Y的邻接向量,它的第i个分量为0(或1),对应于v与y的第i个顶点不邻接(或邻接)。若d_Y(u)=d_Y(v),称u,v,关于Y等度;若u,v(?)Y,且u(Y)=v(Y),称u,v,关于Y     

Hamilton图的一个充分条件

设G=G(V,E)为简单图。d(u)表G中顶点u的度,d(u,v)表顶点u与v的距离。ω(G)表G的分支个数。本文证明了下述定理。 定理 阶数n≥3的简单图G满足下述两条件:     

Ore-2型图中存在两个边不相重的Hamilton圈

本文讨论的图都是无向的简单图。设G是一个图,分别用V(G)和E(G)表示图G的顶点集和边集。又设“、v∈V(G),用d(v)表示v的次数,用vu表示连结u、v的边。     

2连通无爪图的最长圈

本文所涉及的图都是有限无向简单图。设G是一个图,总用V(G)、E(G)、c(G)分别表示G的顶点集、边集、周长,而令p=|V(G)|。设U(?)(G),总用G[U]表示G中由U导出的子图。如果对于任意U(?)V(G),总有G[U](?)K_(1,3),则称G为无爪图。设λ=min{d(u)+d(v)|u,v∈V(G),uv(?)E(G)},δ=min{d(u)|u∈V(G)},其     

关于连通图幂中边不交1-因子

我们总假设G=(V,E)为p阶连通简单图,n为自然数.G的n次幂图G~n定义如下:V(G~n)=V(G),E(G~n)={uv:d_G(u,v)≤n,u,v∈V(G)},式中d_G(u,v)是u和v在G中的距离. 1984年,Nebesk(?)证明了:当P为偶数     

2-连通图的最长圈

设G=(V,E)是一简单、无向图,|V|=n,记N_i(u)={x∈V|d(x,u)=i},i≥1,其中d(x,u)表示点u到点x的距离。 设N_1(u)中点的度序列为d_0~1≥d_1~1≥…≥d_k~1。设N_2(u)中点的度序列为d_1~2≤…≤d_m~2。     

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

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)]     

1坚韧图最长圈的新的充分条件

本文所涉及的图都是有限无向简单图。设G是一个图,用V(G),B和c(G)分别表示G的顶点集、边集和周长,d(u,v)表示u和v间的距离,且设p=|V(G)|。     

关于两类图的整和数

本文中的图均指无向简单图,以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).     

连通、局部连通、无爪图是点泛圈图

本文只讨论有限、无向、无环和多重边的简单图。V(G)、E(G)分别表示图G的顶点集和边集。如果S(?)V(G),用G[S]表示子集S在G中的导出子图。若u∈V(G),N(u)表示u点的邻域,即邻接于u点的全体顶点的集合。     

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的独立集},     

m-k_n×k_s残留图

本文将讨论m-k_u×k_s残留图。定义1 图G=(V,E)为简单图,u∈V,集合N~*(u)={v∈V|v与u邻接}U{u}叫做u的闭邻域。定义2 G叫做F残留图,F是指定的图,如果对每一点u∈V(G),G-N~*(u)≌F,(≌表示同构)递归地定义,图G叫做是m-F残留图,如果对     

冠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的一个协调标号。若上述映射导出     

关于边不交的Hamiltoh圈

本文所讨论的图均为无向的简单图。用δ(G)表示图G的最小度。一个图G称为Ore-(k)型图,如果任一对不相邻顶点“和v都有d(u)+d(v)≥|V(G)|+k(k为整数)。     

图的联结数及其三角形

简单图G的联结数记作bind(G),它是满足下式的最大实数C。这里V(G)是图G的顶点集,N(u)表示图G中与顶点u相邻接所有顶点作成的集合。     

一个Ringel猜想的证明

本文仅讨论简单无向图.图G被称为是一个极大平面二部图(以下简称为mpb图),如果:1)G是二部图.2)G是平面图.3)若u,v∈V(G),(u,v)∈E(G),则G+(u.v)或者不满足1)或者不满足2).为简便,不防将本文所提到的平面图本身视为它的一个平面嵌入.设H是G的一个边导出子图.H在G中的边补图,记为(?),定义为E(G)\E(H)在G中的边导出子图.特别地,如果T是G的一棵树,称(?)为T在G中的上树.     

变分不等式的并行Schwarz算法

设Ω为R~d中有界多角形区域,V为Sobo1ev空间H~k(Ω)的子空间,a(·,·)为V×V上连续强制对称双线性型,f∈V。为简单计,设V中元素在Ω上满足齐次边界条件。考虑变分不等式:求u∈K使 a(u,v—u)≥f(v—u), (?)v∈K, (1) 其中 K={v∈V:v≥φ于Ω},φ≤0于(?)Ω, (2) 或者 K={v∈V:φ≤v≤ψ于Ω}, φ≤0≤ψ于(?)Ω, (3) 且φ,ψ∈H~1(Ω)∩C~0(Ω)。 设V~h(?)H_0~1(Ω)是V的有限元逼近且其结点参数值包含在结点的函数值。问题(1),(2)或问题(1),(3)的有限元逼近为:求u_h∈K_h使     

哈密顿道路图

图G的哈密顿道路图H(G)是和G具有相同顶点集的图,并且其中任意两个顶点u和v是邻接的当且仅当G含有一条哈密顿u-v道路。本文呈现出哈密顿图同构于哈密顿道路图的特征。     

图的连通度与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~-分     

图的联结数及其泛圈性

简单图G的联结数记作bind(G),它是满足下式的最大实数c:■这里V(G)是图G的顶点集,表示图G中与顶点u相邻接的所有点作成的集合。 1973年Woodall提出一个重要的猜想: