Fuzzy超图及其顶点度

<正> 一引言对于Fuzzy超图,A·Kaufmann曾在[1]中给出了一个定义,本文考虑到吴望名在[2]中关于Fuzzy图定义的思想方法更有利于体现图的特点,另给出了一个Fuzzy超图的定义,此定义比[1]中的定义更广。然后将[2]中关于Fuzzy图的α割图,分解定理等推广到了Fuzzy超图,文章的后一部分     

复合图点列表着色的可选性

r部完全图Km*r是完全图Kr与空图Sm的复合图Kr[Sm] . Erdo。s P, Rubin A L和Taylor H在[1]提到了确定Kr[Sm]的点列表着色的可选性的问题并证明了ch(Kr[S2]) = r .Kierstead H A[2]证明了ch(Kr[S3]) =[(4r - 1)/3] .假定Gm是圈Cn与空图Sm的复合图Cn[Sm] .考虑了Gm的列表着色的可选性并证明了ch(G2) =3, ch(G3)≤ 4及在n是奇数时, ch(G3) = 4 .     

115—三次图的结构和124—三次图的存在唯一性定理

对abc—三次图的存在定理与某些特殊图类的结构,[1]、[2]、[3]中已作了一些讨论,本文的目的是讨论其中未解决的115—三次图和124—三次图的结构。所用概念与记号均与[1]、[2]、[3]相同,其它概念和记号见[4],所有图中的实线表示E(L)中的棱,虚线表示E(G)—E(L)中的棱。一、115—三次图的结构引理1 设G是一个115—三次图,L是它的最大二部分子图,则L中任一长为5的初等路必定含在L的一个6回中。     

论abc—三次图

G.Malle在《论最大二部分子图》一文中提出了关于abc—三次图的一些问题,他指出了111—三次图是连通二部分三次图,并证明了不含三角形的图是222—三次图的充要条件是图为彼得松图或十二面体图,他还指出,对其它abc—三次图的特征是尚未解决的问题。本文解决了在“无三角形”限制下abc—三次图的存在性及最小图,以及不加任何限制的abc—三次图的存在性及最小图。本文及我们的[5][6][7]三文基本上解决了G.Malle提出的问题,同时也证实了他关于“可能某些abc—三次图不存在”的说法, 一、无三角形abc—三次图的存在性及最小图本文使用[1]及[2]的有关术语及记号。图G的子图H称为G的最大二部分子图,若对G的任意二部分子图H′,都有ε(H′)≤ε(H),这里ε表示图的棱数。     

超图的连通度（英文）

一个连通图或连通超图的连通度是使得图或者超图不连通所需要去掉的最小点数.显然,一个图(超图)的连通度κ不超过它的最小度δ.如果κ=δ,则图(超图)称为极大连通的.在本文中,我们给出了一致、线性、边传递(点传递)连通超图和连通无钻石超图的极大连通性问题.     

一类树的伴随多项式的分解及其补图的色等价性

设Pn和Cn是具有n个顶点的路和圈,nG表示n个图G的不相交并。令S*r（m+1）+1表示rPm+2的每个分支的一个1度点重迭后得到的图,E■表示把Pm的一个1度点与S*r（m+1）+1的r度点重迭后得到的图,可简记为E■,δ=（r+1）m+r;设n（≥4）是偶数,λ=（n+1）+2-1（n+2）δ,令图P■是表示把2-1（n+2）E■的每个分支的r+1度顶点分别与Pn+1的下标为奇数的2-1（n+2）个顶点重迭后得到的图,运用图的伴随多项式的性质,讨论了图簇E■∪rK1、P■∪E■和P■∪2E■∪rK1的伴随多项式的因式分解式,进而证明了这些图的补图的色等价性。     

Y2,2,λ*形树的伴随多项式的分解及其补图的色等价性

设Pn和Cn是具有n个顶点的路和圈,nG表示n个图G的不相交并。令S*r（m+1）+1表示rPm+2的每个分支的一个1度点重迭后得到的图,■表示把Pm的一个1度点与S*r（m+1）+1的r度点重迭后得到的图,可简记为■,δ=（r+1）m+r;设n（≥3）是奇数,λ=n+2-1（n+1）δ,图■表示把■的每个分支的r+1度顶点分别与Pn的下标为奇数的2-1（n+1）个顶点重迭后得到的图,Y*（2,2,2λ+1）表示把■的两个r+2度点分别与2P3的两个2度点重迭后得到的图,运用图的伴随多项式的性质,讨论了图簇■和■的伴随多项式的因式分解式,令n=2k-1q-1,λk=（2kq-1）+2k-1qδ,讨论了图簇Y*（2,2,λk）∪K1和Y*（2,2,λk）∪（k-1）K1的伴随多项式的因式分解式,进而证明了这些图的补图的色等价性。     

关于Zaks的一个4-度4-连通图的注记

设G为哈密顿图,d(G)表示每对哈密顿圈至少具有d(G)条公共边。按文献[1]定义r(4)=lim sup{d(G)/V(G):G是4-度4-连通哈密顿图}。 对于平面图的情况,定义同此,记作r~*(4)。Zaks曾证明r(4)≥1/16和r~*(4)≥1/20,本文证明可改善到r(4)≥1/8和r~*(4)≥1/10。为此先阐明两个引理。未定义的术语和符     

133—三次图的结构

在[1]中引入了abc—三次图的概念,但仅讨论了两类特殊abc—三次图的结构,本文的目的是解决133一三次图的结构问题。我们用G表示一个连通、无自环、非K_4的三次图,L表示G的最大二部分子图,若S是G的顶点集V(G)的一个子集,则K=[S,]表示G的一个棱截,截指标c(K,L)定义为: c(K,L)=|K∩L|-|K-L|=|L|-|KL|,其中“”表示对称差。本文引用的其它概念与记号见[1]、[2]、[3]。为了叙述方便,我们将133—三次图G的最大二部分子图L的顶点分划集X、Y以两种不同的染色,两个顶点不同色即指它们分属L的不同顶点分划集合。     

P■形图的伴随多项式的分解及其补图的色等价性

设P_n和C_n是具有n个顶点的路和圈,nG表示n个图G的不相交并。令S~*_(r(m+1)+1)表示rP_(m+2)的每个分支的一个1度点重迭后得到的图,E■表示把P_m的一个1度点与S~*_(r(m+1)+1)的r度点重迭后得到的图,可简记为E■,δ=(r+1)m+r;设n(≥3)是奇数,λ=n+2~(-1)(n+1)δ,图P■表示把2~(-1)(n+1)E■的每个分支的r+1度顶点分别与P_n的下标为奇数的2~(-1)(n+1)个顶点重迭后得到的图,运用图的伴随多项式的性质,讨论了图簇E■∪rK_1、P■∪K_1和P■∪E■的伴随多项式的因式分解式,令n=2~(k-1)q-1,λ_k=(2~kq-1)+2~(k-1)qδ,讨论了图簇P■和P■∪(k-1)K_1的伴随多项式的因式分解式,进而证明了这些图的补图的色等价性。     

Y(4,λ)形图簇的伴随多项式的分解及其补图的色等价性

设Pn和Cn是具有n个顶点的路和圈,Sn是n个顶点的的星图,nG表示n个图G的不相交并。EG(r+1)p+r表示把星Sr+1的r个1度点分别与rG的每个分支的第i个顶点重迭,同时把Sr+1的r度点与另一个G的第i个顶点重迭后得到的图,可简记为EGδ,δ=(r+1)(p+r);设m是自然数,图PEG(2 m+1)+(m+1)δ是表示把(m+1)EGδ的每个分支的r+di度顶点分别与P2 m+1的下标为奇数的m+1个顶点重迭后得到的图,记λ=(2 m+1)+(m+1)δ,图Y(4,λ)表示把PEG(2 m+1)+(m+1)δ的两个r+di+1度点与2P3的两个2度点重迭后得到的图,运用图的伴随多项式的性质,讨论了图簇Y(4,λ)∪K1(m为奇数)和Y(4,λ)∪EGδ(m为偶数)的伴随多项式的因式分解式,令m=2k-1 q-1,λk=(2kq-1)+2k-1 qδ,讨论了图簇Y(4,λk)∪(k-1)K1和Y(4,λk)的伴随多项式的因式分解式,进而证明了这些图的补图的色等价性。 更多还原     

列表双临界图（英文）

G是k-可着色的连通图,如果对于G中的所有边uv,都有G-u-v是(k-2)-可着色的,则称图G是双临界图.由Erdo?s和Lova′sz提出了一个长期未能解决的猜想:完全图是唯一的双临界图[1].连通图G称为边双临界图,如果G中包含多对不相邻的边,并且对于任意一对不相邻的边e1,e2,都有χ(G-e1-e2)=χ(G)-2,其中χ(G)表示图G的色数.Kawarabayashi等人[2]及后来的Lattanzio[3]证明了完全图是唯一的边双临界图.文章证明了在图G中,对于任意的两个点u,v∈V(G),如果ch(G-u-v)=ch(G)-2,则图G是完全图,其中ch(G)表示G的选择数,还证明了完全图是唯一的列表双临界图.     

一类w_(λδ)~S形图簇的伴随分解定理及其补图的色等价性

设Pn是具有n个顶点的路,Sδ表示有δ=r+1个顶点的星图,把Pn的n个顶点与nSδ的每一个分支的r度顶点依次重迭后得到的图记为PSnδ,用wS(kn+1)δ表示kPSnδ的每个分支的两个r+1度点与星图S2k+r+1的2k个1度点依次重迭后得到的图,运用图的伴随多项式的性质,讨论了当n=2tq-1≥2时,两类图簇wS(kn+1)δ∪(2k-1)Sδ的伴随多项式的因式分解定理,进而证明了它们的补图的色等价性。     

一类VSλδ形图簇的伴随分解定理及其补图的色等价性

设Pn是具有n个顶点的路,Sδ表示有δ=r+1个顶点的星图,把Pn的n个顶点与nSδ的每一个分支的r度顶点依次重迭后得到的图记为PSλδ,并用VS(kn+1)δ表示kPSnδ的每个分支的一个r+1度点与星图Sr+k+1的k个1度点依次重迭后得到的图.运用图的伴随多项式的性质,讨论图簇VS(kn+1)δ∪(k-1)Sδ的伴随多项式的因式分解定理,进而证明了它们的补图的色等价性.     

关于σ-右理想满足降链条件的环

<正> σ称为结合环R的R一自同态,如果对任意的r∈R,rσ∈R:而且（r1+r2）σ=r1σ+r2σ;（r1 r2）σ=r1σr2在[1]—[2]中对具有σ-结构的环R,讨论了σ-理想理论,得到了相应于古典理想论中的结     

基回数为2的自中心图

Buckley 指出找寻自中心图的特征是一个困难的任务.作为这一工作的开始,找出一些自中心图类看来非常必要.文[1]定理3中证明当 k=■或 n≤k≤[(1/2)n(n-1)]时,n 个顶点 k 条边的自中心图存在.本文建议以基回数为出发点构造自中心图,并确定了基回数为2,即 k-n=1的全部自中心图.本文还纠正了[1]中的一个疏忽.设 G=(V,E)是简单图,u,v∈V(G),d(u,v)为 u,v,两点的距离.定义1 图 G 的半径 r(G)=(_{(v,w)}定义2 图 G 中顶点“的最远距离     

多目标非凸规划解的充分必要条件

本文证明了对于满足三类非凸性条件的几种多目标规划问题,Kuhn—Tucker条件和鞍点条件都是有效解的既充分又必要的条件;推广和发展了文献[1]—[3]的主要结果。     

整函数的[p,q]-φ(r)级与[p,q]-φ(r)型

研究了当整函数f1(z)与f2(z)具有相同的[p,q]-φ(r)增长级和不同的[p,q]-φ(r)型时,研究了f1+f2,f1·f2的[p,q]-φ(r)增长级与[p,q]-φ(r)型,得到了一些结果,完善了原有的一些结果。     

与图的中心有关的两个定理

本文讨论与图的中心有关的问题。使用的一般术语与记号与[1]相同。图G中两顶点x与y之间的距离用d_G(x,y)表示,x的联系数(eccentricity)e_G(x)=(?) d_G(x,y)。G的半径与直径分别记为r(G)=(?) e_G(x)与d(G)=(?) e_G(x)。G中以r(G)为联系数的顶点叫做G的中心点,全体中心点集的诱导子图叫做G的中心,记为c(G)。满足c(G)=G的图G叫做自中心图。首先,我们讨论以任意的图H作为中心的图G的直径与半径之间应满足的关系。     

Euler环游图的连通度

[1]中给出了Euler环游图E_u(G)的定义,并证明了E_u(G)具有边-Hamilton性。[2]中证明了E_u(G)是正则图。本文得到如下结果,对|V(E_u(G)|≥2,E_u(G)的连通度恰好等于其正则度数。