关于P（n1,n2,...nm）和Dm,4的优美性

一个简单图G=(V,E)是k-优美的(k≥1的整数),如果存在一个1-1映射 f:V(G)→(0,1,…,|E| k-1)使得对所有的边e=wv∈E(G),由f~*(u,v)=|f(u)-f(v)|导出的映射 E(G)→{k,k 1,…,|E| k-1}是一个1-1对应。这个关于k-优美的概念是由Slater和Thuillier相互独立地提出来的。当k=1,就是我们通常研究的优美图。显然,k-优美图一定是1-优美图。反之不真。例如,三回路c_3是1-优美图,但对k>1,非k-优美。     

θ*r,s,t-图与唯一2-列表染色图的特征化

如果一个图G存在一个k-列表安排使得G具有一个唯一列表染色,则称 G是唯一列表可染色图,简称UkLC图．我们称图G具有M(k)性质当且仅当G不 是UkLC图．本文在借鉴θr,s,t-图概念的基础上引入θr,s,t-图的定义,并证明:除了 r=s=t=2以外,θr,s,t-图都是U2LC图．利用如上结果我们给出M．Mahdian and E．S．Mahmoodian对U2LC图所作特征化的一个简单证明．     

一类完全多部图的色可选择性

如果一个图G的选择数等于它的色数,则称该图G是色可选择的．在2002年, Ohba给出如下猜想:每一个顶点个数小于等于2X(G) 1的图G是色可选择的．容易发现Ohba猜想成立的条件是当且仅当它对完全多部图成立,但是目前只是就某些特殊的完全多部图的图类证明了Ohba猜想的正确性．在本文我们证明图K6,3,2*(k-6),1*4(k≥6)是色可选择的,从而对图K6,3,2*(k-6),1*4(k≥6)和它们的所有完全k-部子图证明了Ohba猜想成立．     

退化图中的子图计数问题研究

令G表示n个顶点的图,如果G的每个子图中都包含一个度至多为k的顶点,则称G为k-退化图.令N(G,F)表示G中F子图的个数.主要研究了k-退化图中完全子图和完全二部子图的计数问题,给出了计数的上界以及相应的极图.首先,证明了Ν(G,K_t)≤(n-k)(k t-1)+(k t).其次,如果s,t≥1,n≥k+1且s+t≤k,我们证明了Ν(G,K_s,t)≤{(k s)(n-s s)-1/2(k s)(k-s s),t=s,(k s)(n-s t)+(k t)(n-t s)-(k t)(k-t s),t≠s.此外,还研究了在最大匹配和最小点覆盖为给定值的情况下,图G中的最大边数.记v(G),K(G)分别为图G的最大匹配数和最小点覆盖.证明了当v(G)≤k,K(G)=k+r且n≥2k+2r²+r+1时,有e(G)≤(k+r+1 2)+(k-r)(n-k-r-1).     

整数距离图G(Dm,k,2)的点线性荫度

整数距离图G(D)以全体整数作为顶点集,顶点u,v相邻当且仅当|u-v|∈D,其中D是一个正整数集．本文讨论整数距离图的点线性荫度,记为vla(G(D))．对于m≥5k,设D_(m,k,2)={1,2,…,m}/{k,2k),得到vla(G(D_(m,1,2)))=■并决定出了G(D_(m,2,2))在某些特殊的仇值上点线性荫度的确切值以及当k≥3时G(D_(m,k,2))的点线性荫度的上、下界．     

整数距离图G(D_(m,k,2))的点荫度

图G的点荫度va(G)是顶点集合V(G)能划分成的这样一些子集的最少数目,其中任一子集的点导出子图都是森林.整数距离图G(D)以全体整数作为顶点集,顶点u,v相邻当且仅当|u-v|∈D,其中D是一个正整数集.对于m2k≥2,令D_(m,k,2)=[1,m]\{k,2k}.该文得出了整数距离图G(D_(m,k,2))的点荫度的几个上、下界;进而,对于m≥4,有va(G(D_(m,1,2)))=[(m+4)/5];对于m=10q+j,j=0,1,2,3,5,6,有va(G(D_(m,2,2)))=[(m+1)/5]+1.     

二部平衡公平划分的一个下界

设V_1,V_2是图G的一个二部划分.如果一1≤|V_1|-|V_2|≤1,则称V_1,V_2是G的一个二部平衡划分.对于n个顶点m条边的简单图G,本文证明了:(1)若G是k-正则图(k≥3),则G存在一个最小二部平衡划分V_1,V_2,使得max{e(V_1),e(V_2)}≥((k-1)m)/4k;(2)如果r是大于4的实数,且当n是偶数时△(G)≤((3r-4))/(r+4)δ(G)-(2r)/(r+4),当n是奇数时△(G)≤(3r-4)/(r+4)δ(G)-(8r)/(r+4),那么G存在一个二部平衡划分,使得min{e(V_1),e(V_2)}≥m/r,这里e(V_i)表示G中两个顶点都在V_i中的边的数目.     

一类高阶线性微分方程解的增长性

本文讨论一类一般的齐次和非齐次高阶线性微分方程解的增长性,证明了当整函数F,A_j,D_j和s≥1次多项式P_j(z)(j=0,1,…,k-1)满足某些条件时,方程(其中k≥2),f~(k) (A_(k-1)(z)e~(P_(k-1)(z)) D_(k-1)(z))f~((k-1)) … (A_0(z)e~(P_0(z)) D_0(z))f=F当F≡0时,所有非零解具无穷级；当F≠0时,至多除去一个有限级解f_0外,其余所有解均满足■(f)=λ(f)=σ(f)=∞且σ_2(f)≤max{s,σ(F)},从而推广了M．Frei,M．Ozawa,G．Gundersen,J．K．Langley,陈宗煊,李纯红等人的结果。     

一类非线性广义样条最佳L_p逼近的光滑性

设L是常系数n阶线性微分算子,m∈N, 0=s_00适当小,v=1,…,r}本文证明了设f∈L_p[0,1],1≤p<∞,那末当n≥2时,存在f的最佳L_p[0,1]逼近样条(?)∈C[0,1]∩φ~*(m,q)。当n≥3时,存在f的最佳L_p[0,1]逼近样条(?)∈C~1[0,1]∩φ~*(m,q)。     

证明图ρ_n~G(i)∪G等的伴随分解及色等价性

设P_m和C_m分别表示具有m个顶点的路和圈,G是任意的r阶连通图,设m是偶数,把路P_(m-1)的标号为偶数的2~(-1)m个顶点分别与2~(-1)mG每个分支的第i个顶点V_i重迭后的图记为ρ_((m-1)+2~(-1)mr)~G(i),令n=(2m+1)+(m+1)r,把图kρ_n~G(i)的每个分支的一个d(v_i)+1度顶点分别与S_(k+1)的k个1度点重迭后所得到的图记为Y_(kn+1)~(PG),运用图的伴随多项式的性质,首先给出了一类图簇ρ_n~G(i)和Y_(kn+1)~(PG)的伴随多项式.在讨论上述图的伴随多项式的基础上,证明了图ρ_n~G(i)∪G、Y_(kn+1)~(PG)∪(k-1)K_1和Y_(kn+1)~(PG)∪(k-1)K_1∪(k-1)G的伴随多项式的因式分解定理,进而证明了这些图类的补图的色等价性.     

γ-可图序列与γ-完全子图

一个r-图是一个无环的无向图,其中任何两个顶点之间至多被r条边连接.一个m+1个顶点的r-完全图,记为K_(m+1)^((r)),是一个m+1个顶点的r-图,其中任何两个顶点之间恰好被r条边连接.一个非增的非负整数序列π=(d_1,d_2,…,d_n)称为是r-可图的如果它是某个n个顶点的r-图的度序列.一个r-可图序列π称为是蕴含(强迫)K_(m+1)((r)),是一个m+1个顶点的r-图,其中任何两个顶点之间恰好被r条边连接.一个非增的非负整数序列π=(d_1,d_2,…,d_n)称为是r-可图的如果它是某个n个顶点的r-图的度序列.一个r-可图序列π称为是蕴含(强迫)K_(m+1)^((r))可图的如果π有一个实现包含K_(m+1)((r))可图的如果π有一个实现包含K_(m+1)^((r))作为子图(π的每一个实现包含K_(m+1)((r))作为子图(π的每一个实现包含K_(m+1)^((r))作为子图).设σ(K_(m+1)((r))作为子图).设σ(K_(m+1)^((r)),n)(τ(K_(m+1)((r)),n)(τ(K_(m+1)^((r)),n))表示最小的偶整数t,使得每一个r-可图序列π=(d_1,d_2,…,d_n)具有∑_(i=1)((r)),n))表示最小的偶整数t,使得每一个r-可图序列π=(d_1,d_2,…,d_n)具有∑_(i=1)ⁿ d_i≥t是蕴含(强迫)K_(m+1)n d_i≥t是蕴含(强迫)K_(m+1)^((r))-可图的.易见,σ(K_(m+1)((r))-可图的.易见,σ(K_(m+1)^((r)),n)是Erds等人的一个猜想从1-图到r-图的扩充且τ(K_(m+1)((r)),n)是Erds等人的一个猜想从1-图到r-图的扩充且τ(K_(m+1)^((r)),n)是经典Turan定理从1-图到r-图的扩充.本文给出了蕴含K_(m+1)((r)),n)是经典Turan定理从1-图到r-图的扩充.本文给出了蕴含K_(m+1)^((r))的r-可图序列的两个简单充分条件.此两个条件包含了Yin和Li在[Discrete Math.,2005,301:218-227]中的两个主要结果和当n≥max{m((r))的r-可图序列的两个简单充分条件.此两个条件包含了Yin和Li在[Discrete Math.,2005,301:218-227]中的两个主要结果和当n≥max{m²+3m+1-[(m2+3m+1-[(m²+m)/r],2m+1+[m/r]]}时,σ(K_(m+1)2+m)/r],2m+1+[m/r]]}时,σ(K_(m+1)^((r)),n)之值.此外,我们还确定了当n≥m+1时,τ(K_(m+1)((r)),n)之值.此外,我们还确定了当n≥m+1时,τ(K_(m+1)^((r)),n)之值.     

若干并图的优美标号

证明了,对任意大于1的自然数m,n,p,非连通图(■ V ■)∪K_(n,p)是优美图;当k≤p,m=kn+3或m=kn+1时,非连通图(P_2 V ■)∪K_(n,p)是优美图;当p≥2,m=3k+1时,非连通图(P_2 V ■)∪K_(3,p)是优美图;对任意正整数n,p,非连通图(P_1 V P_(2n+2))∪_(n,p)是优美图.     

哈密尔顿性和部分平方图的独立集

设G是一个图,G的部分平方图G*满足V(G*)=V(G),E(G*)=E(G)∪{uv:uv■E(G),且J(u,v)≠■},这里J(u,v)={w∈N(u)∩N(v):N(w)■N[u]∪N[v]}.利用插点方法,证明了如下结果:设G是k-连通图(k2),b是整数,0min {k,(2b-1+k)/2}(n(Y)-1),则G是哈密尔顿图.同时给出图是1-哈密尔顿的和哈密尔顿连通的相关结果.     

无K_4-图子式的图的邻和可区别边染色

给定图G的一个正常k-边染色φ:E(G)→{1,2,…,k},记f(v)是与点v相关联的边的颜色的加和.若对G的每条边uv都有f(u)≠f(v),则称φ是图G的k-邻和可区别边染色.图G存在k-邻和可区别边染色的k的最小值称为图G的邻和可区别边色数,记作χ'_Σ(G).运用组合零点定理研究了△≥6的无K_(4-)图子式的图的邻和可区别边色数,证得若G不含相邻最大度点,则χ'_Σ(G)=△,否则χ'_Σ(G)=△+1.     

完备图分拆为带一条弦的(2k-1)-长圈

本文给出了构造G-设计的一个统一方法及当v≡1(mod 4k)时的C_(2k-1)~((r))-GD(v)的存在性,其中C_(10)~((r)),1≤r≤k-2表示带一条弦的2k-1长圈,r表示弦两个端点间的顶点个数。     

若干图的强染色

图 G(V,E)的一正常 k-染色 σ称为 G(V,E)的 - k-强染色当且仅当对任何两个不同顶点 u和 v,只要d(u,v)≤ 2 ,则 u、v染不同颜色 (这里 d(u,v)表示 u,v之间的距离 ) ,并称 xs(G) =min{ k|存在 G的 - k-强染色 }为 G的强色数 ,本文得到 θ-图 ,Cm,n图 ,Halin图的强色数 xs(G)     

正则的哈密顿路图

本文仅考虑无向简单图。所谓图G的哈密顿路图是指这样的图,它与G有相同的节点集,其中任意两个节点有边相连当且仅当它们在G中有哈密顿路相连。用H(G)表示图G的哈密顿路图。递归地,由H~k(G)=H(H~(k-1)(G))(k≥2)可以定义k-哈密顿路图。用ε(G)表示图G的边数。如果G(?)H~k(G),则称图G为k-自哈密顿路图,简称为k-SHP图(k-Self Hamil-tonian Path Graph(k≥1)。若k=1,则称G为SHP图。     

可圈的一个充分条件

本文我们证明如下结果:设G=(V,E)是一个n(n≥3)阶k-连通(k≥2)图,记X1,X2,…,Xk为V的子集,X=X1∪X2∪…∪Xk.若对每个I,I=1,2,…,k,满足:对任意的u,v∈Xi,有d(u) d(v)≥n或|N(u)∪N(v)|≥n-δ或|N(u)∩N(v)|≥α,这里δ是G的最小度,α是G的独立数,则G是X-可圈的.     

平面图的(3,1)~*-可选择性

若对图G的任何一个满足|L(v)|=k的列表配置L,存在G的一个L-染色c使G的每个顶点v至多有d个邻点和v染相同的颜色,则称图G是(k,d)~*-可选的.本文证明了:(1)若G是i-圈和j-圈(i,j∈{3,4})不相交的平面图,则G是(3,1)~*-可选的.(2)不含6圈和相交3-圈的平面图是(3,1)~*-可选的.     

若干图的点强全着色

图G(V,E)的一正常k-全着色σ称为G(V,E)的一个k-点强全着色,当且仅当v∈V(G),N[v]中的元素着不同颜色,其中N[v]={u|vu∈E(G)}∪{v}.并且vχsT(G)=min{k|存在G的一个k-点强全着色}称为G(V,E)的点强全色数.本文得到了一些特殊图的点强全色数χvTs(G),并提出猜想:对于简单图G,有k(G)≤χvTs(G)≤k(G)+1,这里k(G)表示图G中所有顶点间距离不超过2的点集的最大顶点数.