图Kn-E(Kr),Kr(*)Kn的和数σ与整和数ζ的关系

针对1994年F.Harary提出的关于和图与整和图的未决问题,对Kn-E(Kr),KrKn,详细讨论了ζ(Kn-E(Kr))与σ(Kn-E(Kr))的关系,并对任意的n,r,n≥r≥1,给出了其完整的结果.     

图Kn-E(Kr),Kr(∪)Kn的整和数

Z表示所有整数的集合.一个有限子集S(∪)Z上的整和图是指图(S,E)中uv∈E当且仅当u+v∈S.图G是整和图,如果它同构于某个子集S(∪)Z上的整和图.图G的整和数是指使(G∪mK1)成为一个整和图时加入的孤立顶点的最少个数m.1994年Harary在[3]中提出了4个未决的问题,本文完整地回答了其中的第一个问题,即确定了图(Kn-E(Kr))的整和数.具体结论如下:ζ(Kn-E(Kr))={0(r=n,n-1)n-1(n-2≥r≥[2n/3]-1)3n-2r-4([2n/3]-1＞r≥n/2)2n-4([2n/3]-1＞n/2≥r≥2)其中n≥5,r≥2,[x]表示不小于x的最小整数.     

图K_n—E(K_r),K_rK_n的整和数

Z表示所有整数的集合。一个有限子集SZ上的整和图是指图（S,E）中uv∈E当且仅当u＋v∈S。图G是整和图,如果它同构于某个子集SZ上的整和图。图G的整和数是指使（GmK1）成为一个整和图时加入的孤立顶点的最少个数m。1994年Harary在[3]中提出了4个未决的问题,本文完整地回答了其中的第一个问题,即确定了图（Kn－E（Kr））的整和数。具体结论如下：其中n≥5,r≥2,[x]表示不小于x的最小整数。     

Gn,n的和数

摘要：整数集合的非空有限子集S的和图是(S，E)，E=(uv:u≠v,u v∈S),图G的和数σ（G）=min(m≥0:存在（S.E）≌GUmK1)，证明了σ（Gn,m）=2n 1(n≥2)。     

图Kr,s-E（rK2）的（模,整）和数

令N(Z)表示正整数(整数)集,N(Z)的非空有限子集S的和图G (S)是图(S,E),其中uv∈E当且仅当u v∈S;一个图G称为(整)和图,若它同构于某个SN(Z)的和图,(整)和数σ(G)(ζ(G))是使得G∪nK1是(整)和图的非负整数n的最小值。模和图是取SZm\{0}且所有算术运算均取模m(≥│S│ 1)的和图。一个图G的模和数ρ(G)是使得G∪ρK1是模和图的孤立点数ρ的最小值。对图Kr,s-E(rK2)(s>r≥4且s≥6)。研究了它的(模,整)和数,文中确定了图K4,5-E(4K2)的(模,整)和数。     

两类图的和数

研究了两类完全多部图的和数，证明了图K1，1，r和K1，1，1，r（r≥3）的和数分别是r和r＋2．     

伞Jn的模和数与整和数

给出了模和图JnU rK1的一些性质,并证明了当n≥6且n为偶数时,ρ(Jn)=1及当n≠3时,伞Ln是整和图.     

芭蕉扇的模和数

芭蕉扇Tn指在扇Fm=Pn∨K1的轴K1上悬挂一条边所得图，模和图是取S∈Zm＼{0}且所有算术运算均取模m（≥｜S｜＋1）的和图，一个图G的模和数ρ（G）是使得GUrK1是模和图的孤立点数r的最小值．该文给出了模和图TmUrK1的一些性质，并证明了当n≥3时，ρ（Tn）=1．     

蕴含K3,s-ke的可图序列

考虑经典Turán型问题的变形:确定最小的正偶数σ(Kr,s-ke,n),s≥r≥k≥1,使得对于每一个n项可图序列π=(d1,d2,…,dn),当σ(π)=d1 d2 … dn≥σ(Kr,s-ke,n)时,π是蕴含几乎完全二部图Kr,s-ke可图的,即Kr,s-ke是从完全二部图Kr,s中删去k条边后所得的图,而这k条边构成Kr,s的一匹配.然后确定出当r=3,s≥4且n充分大时,σ(Kr,s-ke,n)的值.     

芭蕉扇的细分图T*n的和数

芭蕉扇Tn指在扇Fn=Pn∨K1的轴K1上悬挂一条边所得的图,该边叫Tn的柄,Pn上的边叫缘边,其余边叫辐.芭蕉扇细分图T*n是Tn的缘边各剖分一次所得的图.本文证明了芭蕉扇细分图T*2是模和图,且σ(T*n){=1,n=2、3,≤2,n≥4     

芭蕉扇的细分图T*n的和数

芭蕉扇Tn指在扇Fn=Pn∨K1的轴K1上悬挂一条边所得的图,该边叫Tn的柄,Pn上的边叫缘边,其余边叫辐.芭蕉扇细分图T*n是Tn的缘边各剖分一次所得的图.本文证明了芭蕉扇细分图T*2是模和图,且σ(T*n){=1,n=2、3,≤2,n≥4     

棱柱的排斥和数

基于图G的排斥和数ε（G）是使得G∪nK1为排斥和图的非负整数n的最小值,给出了棱柱的定义,并证明了当n≥3时,棱柱的排斥和数等于5.     

芭蕉扇的细分图T_n~*的和数

芭蕉扇T_n指在扇F_n=P_n(?)K_1的轴K_1上悬挂一条边所得的图,该边叫T_n的柄,P_n上的边叫缘边,其余边叫辐。芭蕉扇细分图T_n~*是T_n的缘边各剖分一次所得的图。本文证明了芭蕉扇细分图T_2~*是模和图,且σ(T_n~*)(?)=2,n=2、3,≤2,n≥4     

蕴含Kr,s,t可图序列的一个极值问题

Gould,Jacobson和Lehel考虑了下述经典Turán型极值问题的一个变形对于给定的图H,确定最小的偶数σ(H,n),使得每一个n项可图序列π=(d1,d2,…,dn),当σ(π)=d1+d2+…+dn≥σ(H,n)时,π都有一个实现G包含H作为子图.本文确定了σ(K1,2,2,n),8≥n≥5,及当n≥6时,σ(K2,2,2,n)之值,其中Kr,s,t是r×s×t完全三部图.     

梯子的模和数

本文证明了kL3(k≥2)是模和图,因而也是模整和图.     

蕴含K1，1，3的正可图序列的最小度和

Gould R J等人考虑了下述经典Turán型极值问题的变形对于给定的图H,确定最小的正偶数σ(H,n),使得对于每一个n项正可图序列π=(d1,d2,...,dn),当σ(π)=d1+d2+...+dn≥σ(H,n)时,π有一个实现G以H作为子图.本文完全确定了σ(K1,1,3,n)之值,其中Kr,s,t是r×s×t完全三部图.     

二正则图的和数

设S是自然数集N*的一个有限集.定义在S上的和图G~+(S)是图(S,E),满足uv∈E当且仅当u+v∈S.称一个图G为和图,如果存在一个S,使得G≌G~+(S).对于一个图G,称使得G∪r K_1是和图的最少的孤立点的个数r为G的和数.和图的概念首先是由Harary提出来的,并且他指出除了C_4的和数为3外,所有的圈C_n的和数都是2.本文研究了全部二正则图的和标号问题,证明除了C_4外所有的二正则图的和数都是2.     

两类图的排斥和数

本文研究了两类图P1n和P2n的排斥和数,指出了这两类图的排斥和数就是它们的最大度数,并给出了它们的排斥和标号.     

圈与K4的临界完全图Ramsey数

对给定的2个图G和H,Ramsey数r(G,H)是最小的正整数r,使得对完全图Kr的边任意红蓝着色或存在红色子图G、或存在蓝色子图H.临界完全图Ramsey数r_K(G,H)是最大的正整数n,使得图K_r-K_n的边任意红蓝着色或存在红色子图G或存在蓝色子图H.当正整数n≥5时,r_K(C_n,K_4)=n/2,C_n为n个点的圈.     

Sierpiński-like图的条件着色

分别对Sierpiński-like图的条件着色进行研究,分别给出S~+(n,k)图与S~(++)(n,k)图的条件色数.对于S+(n,k)图,当n≥2时,若1≤r≤k-1,则χ_r(S~+(n,k))=k;若r≥k,n为奇数时,χ_r(S~+(n,k))=k+1,n为偶数时,χ_r(S~+(n,k))=k+3.对于S~(++)(n,k)图,当n≥2时,若1≤r≤k-1,则χ_r(S~(++)(n,k))=k;若r≥k,χ_r(S~(++)(n,k))=k+1.