曲面嵌入图的圈基

圈基常用于描述图的圈结构.在实际应用算法中,算法的复杂度取决于圈基的选择.圈基的长,即其包含的边数,直接影响算法的速度.2-连通图G圈基长的一个下界是2 |E (G)|-|V (G)|,其中V (G)和E (G)分别是顶点集和边集.若图G包含长为2 |E (G|)-|V (G)|的圈基,则它是平面图.本文应用曲面嵌入图理论将这一结果推广至曲面嵌入图上.     

求二分图所有最小复盖的交的好算法以及由此求所有最小复盖的算法

本文给出了一个求二分图G所有最小复盖的交的好算法,其时间复杂性为O(max{|V(G))|~(1/2)。|E(G)|,|V(G)|~2})。并且在上述基础上再给出求所有最小复盖的算法,其时间复杂性为O(max{|V(G)|~(1/2)·|E(G)|,|V(G)|~2,|C|·|V(G)|})。其中V(G),E(G)分别是G的顶点集,边集,C是G的最小复盖组成的集     

求二分图所有最小复盖的交的好算法以及由此求所有最小复盖的算法

本文给出了一个求二分图G所有最小复盖的交的好算法,其时间复杂性为O(max{|V(G)|~(1/2)。|E(G)|,|V(G)|~2})。并且在上述基础上再给出求所有最小复盖的算法,其时间复杂性为O(max{|V(G)|~(1/2)·|E(G)|,|V(G)|~2,|C|·|V(G)|})。其中V(G),E(G)分别是G的顶点集,边集,C是G的最小复盖组成的集     

偶圈冠图r-C_n的奇优美性及奇优美性算法

图G的一个奇优美标号是指存在一个双射函数L:V(G)→{0,1,2,…,2|E|-1}使得任意边e=uv∈E(G),由L′(e)=|L(u)-L(v)|决定的边标号L′为E(G)到{1,3,…,2|E|-1}的双射。根据奇优美图的定义,文章讨论了偶圈冠图r-Cn的奇优美标号问题,证明了当n≡0(mod 4)时,偶圈冠图r-Cn是奇优美图,给出的新奇优美标号算法不同于现有的文献结果。     

联图P_m ∧ P_n的符号星控制数

偶度二部图的边可分拆为若干偶圈之并,且任意一个无向简单图G,有|E(G)|-γ'ss(G)为偶数。本文确定了联图Pm∧Pn的符号星控制数。     

若干倍图的Smarandachely邻点边染色

图G(V,E)的Smarandachely邻点边色数是满足条件uv∈E(G),|C(u)＼C(v)|≥1并且|C(v)＼C(u)|≥1的一个正常边染色的最小边色数,其中C(u)=｛f(uv)|uv∈E(G)｝。给出了路、圈、星、扇图的倍图的Smarandachely邻点边色数。     

Hamilton图中的H圈数

设Гk={G||E(G)|—|V(G)|=k且G是至少有3个顶点的H图}，Гn,k={G|G是阶为n≥3的图且|E(G)|—|V(G)|=k}，用，(G)表示图G的H圈数，令h(k)=max{f(G)|G∈Гk}和h(n，k)=max{f(G)|G∈Гn,k}，作者得到h(是)的上界和下界，并且当n为大于等于k的奇数以及k≤号 l时，确定了h(n，k)。     

K连通图的k分割多项式算法

图G的K分割问题可描述为:输入(Ⅰ)G=(V,E),G为简单无向图,其中|V|=n,|E|= m;(Ⅱ)a_1,a_2,…,a_k k个G中不同的顶点;(Ⅲ)n_1,n_2,…,n_k k个正整数满足 n_1+n_2+…,+n_k= n.输出(V_1,V_2,…,V_k),对1≤i≤k,满足(Ⅰ)a_i∈V_i;(Ⅱ)G[V_i]是连通图;(Ⅲ)|V_i|=n_i.本文给出时间复杂性为O(knm)通用K连通图的k分割多项式算法.     

2-连通图的最长圈

设G是2-连通图,λ(G)=min{d(u)+d(v)|u,v∈V(G),uv■E(G)},本文证明了除六类图外,G中最长圈的长c(G)≥min{|v(G)|,λ+2}。     

至多有2个等长圈的简单图的最大边数

设Sn是具有n个顶点至多有2个等长圈的简单图的集合。若Sn中不存在图G’使|E(C’)|>|E(G)|,Ng称G是简单的最大图分布(2)图(简记为简单MCD(2)图)。用f~*(n,2)表示具有n个顶点的简单MCD(2)图的边数。作者证明了f~*(n,2)≥(n-l)+[1/2(11n-20)~(1/2)]且当3≤n≤10时等式成立。     

关于Catlin—猜想的反例

Catlin的2／3－猜想：若G是超欧拉图，G≠K1，那么G有一个欧拉生成子图H，使得|E(H)|≥2／3|E(G)|。给出了Catlin的2／3－猜想的一些反例。     

圈和分数[a,b]-因子

设1≤a，a 2≤b是整数,设G是一个具有圈c的图，且其阶|G|≥(a b)(2a b 1)／b,当δ(G)≥a 2且max|dG(x)，dG(Y)|≥a|G|／(a b) 2对每一对G中不相邻的两点x和y都成立,那么G有一个分数[a，b]一因子F使得E(F)∩E(C)=Ф,这个度条件下的下界是紧的。作为推论，我们得到具有哈密顿圈C的图有一个[a，b]一因子F使得E(C)真包含E(F)的一个度条件。     

广义圈的同构因子分解

广义圈是一个简单图G＝(V，E)，其中点集V＝V0∪…∪Vn-1,|V0|=…=|Vn-1|，边集E=|uv|u∈Vi,v∈Vi=1,i=0,…，n-1,i 1=mod(n)|，证明了广义圈可以分解为t个同构因子的充要条件是t可以整除该广义圈的边数．     

一阶偏微分方程组的斜微商问题解的微分性质及解的存在定理

在空间W_p~((1))中,对于非线性方程组(A)W_z~-=g(z,W,W_z),|z|<1,|g(z,W,W_2~1)-g(z,W,W_z~2)|≤q_0|W_z~1-W_z~2|,q_0=const<1, 我们建立了斜微商问题的广义解的存在性和存在唯一性定理。对于线性方程组(A)W_z~-=q_1(z)W_z q_2(Z)W_z A(Z)W B(z)W C(z),|q~1(z)| |q~2(z)|≤q_0<1,q_0=const, 我们建立了斜微商问题广义解和连续可微解的存在唯一性定理,广义解的谱理论,并且研究了广义解的可微性。     

边染色图中的2-因子

令G是含n个点的边染色图,对G中任意顶点x,定义其色邻域CN(x)为集合{c(xy)|xy∈E(G),y∈V(G)}.如果G中任意相邻的两条边都染有不同的颜色,就称G是正常染色的.证明了如果边染色图G满足对V(G)中任意两点u,v有|CN(u)∪CN(v)|≥4n/3+8,则图G含有一个正常染色2-因子.     

2-连通图过指定边的长圈

对2-连通非完全图G，令μ(G)=min{max{dG(v)}|dG(u,v)=2}．一个著名的范定理;每一个2-连通非完全图G包含长至少为min{|V(G)|，2μ(G)}的圈．在这篇论文中我们证明了：若G是2-连通无三角形图，则通过G的任一边存在长至少为min{|V(G)|，2μ(G)}的圈．     

2-连通［4,2]-图中的圈

如果图G中任意s个点的导出子图至少含有t条边，则称图G为［s,t］-图. 设是2-连通［4,2］-图，C是G中满足|V(C)|＜|V(G)|的任一圈，则或者G中有(|C|+1)-圈，或者G同构于K_2,3,K_1,1,3,F₁,F₂,F₃,F₄,F₅之一.     

2-连通图中点不交路的划分问题

给定一个阶为n的2-连通图G=(V;E)及一个正整数k,考虑在邻域并条件下G被分成k条点不交路的问题,得到下面的结果,对G中任何四个独立点x1,x2,y1,y2∈V,满足|NG(x1)∪NG(x2)| |NG(y1)∪NG(y2)|n-k,则G能被分划分k条点不交的路.     

图Fm△↓Sn的边色数和邻强边色数

对图G的一个正常的k边染色法f，若A↓e∈E(G)，e=uv，{f(uw)|uw∈E(G))≠{f(vw)|vw∈E(G))，则称f为G的一个k-邻强边染色法，k的最小值称为G的邻强边色数．V(Fm△↓Sn)={w}∪{ui|i=1、2，…，m}∪{vv|i=1，2，…，m；j=1，2，…，n)，E(Fm△↓Sn)={wui|i=1，2，…．m}∪{uivu|i=1，2，…，m；j=1，2，…，n}∪{uiui |i=1，2，…，m-1)．本文得到了Fm△↓Sn的边色数和邻强边色数．     

伞状树的奇强协调性

设G=V,E是一个简单图,若存在一个映射f:V(G)→{0,1,2,…,2|E|-1}满足(1)对任意的u,v∈V,若u≠v,则f(u)≠f(v);(2)对任意的e1,e2∈E,若e1≠e2则g(e1)≠g(e2),此处g(e)=f(u)+f(v),e=uv,且{g(e)|e∈E}={1,3,5,…,2|E|-1},则称G是奇强协调图,f为G的奇强协调标号,讨论了一类树的奇强协调性.