关于Win猜想的部分结果

<正> 本文假定G=(V,E)是2n个点的简单图,我们用C[U]表示点集U的导出子图,用d(x)表示G中点x的次,d_H(x)表示G的子图H中点x的次.其余符号见[3]. 给定非负整数k,若图G中每一对不相邻的顶点u和ν,都有d(u)+d(ν)≥2n+k,则称G为Ore k-型图.S.Win给出下述猜想: 若G是Ore k-型图,则G有k+2个1-因子.其中k≤2n-4.     

具有较小直径的三类图的对极色数

对一个连通图G,令d(u,v)表示G中两个顶点间u和v之间的距离,d表示G的直径.G的一个对极染色指的是从G的顶点集到正整数集(颜色集)的一个映射c,使得对G的任意两个不同的顶点u和v满足d(u,v)+|c(u)-c(v)|≥d.由c映射到G的顶点的最大颜色称为c的值,记作ac(c),而对G的所有对极染色c,ac(c)的最小值称为G的对极色数,记作ac(G).本文确定了轮图、齿轮图以及双星图三类图的对极色数,这些图都具有较小的直径d.     

关于图Pκn的均匀染色

对简单图G=〈V,E〉及自然数k,令V(Gk)=V(G),E(Gk)=E(G)U{uv|d(u,v)=k},其中d(u,v)表示G中u,v的距离,称图Gk为G的k方图.本文讨论了路的k方图Pkn的均匀点染色、均匀边染色和均匀邻强边染色,利用图的色数的基本性质和构造染色函数的方法,得到相应的色数Xev(Pkn),Xec(Pkn),Xeas(Pkn).并证明猜想"若图G有m-EASC,则一定有m+1-EASC"对Pkn是正确的.     

若干图的点强全着色

图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的点集的最大顶点数.     

边色数的分类及其有关性质

设图G为简单连通图,由Vizing定理知:Δ(G)≤x′(G)≤Δ(G) 1,其中Δ(G)表示图G的最大顶点次,x′(G)为图G的边色数。若x′(G)=Δ(G),则称G为第一类图,记为G∈C~1;若x′(G)=Δ(G) 1,则称G为第二类图,记为G∈C~2。其他图论术语见一般参考书。一边e(或者顶点v)称为临界的,如果成立x′(G)>x′(G\e)(或者x′(G)>x′(G\v))。图G称为是临界的,如果G∈C~2,且G的每一边是临界的。对于v∈V(G),令d~*(v)=|{u|(v,u)∈E(G)且d(u)=Δ(G)}|。设F={u|d(u)=Δ(G),u∈V(G)},记G_Δ=G[F]。令图G_Δ的圈秩数为b(G_Δ)。     

哈密顿线图的一个充分条件

对于图G的任意边e=uv,边的度定义为d(e)=d(u)+d(v),其中d(u)和d(v)分别为顶点u和v的度.本文的主要结果是: 设G是几乎无桥的p≥2阶简单连通图,且G(?)K_(1,p-1),若对任意相距为2的两边e_1和e_2,d(e_1)+d(e_2)≥2p-6,则G有一个D—闭迹,从而G的线图L(G)是哈密顿的.     

Halin图的邻和可区别边染色与边权点染色

记[k]={1,2,…,k),称为颜色集.设φ:E(G)→[k]为图G的边集合到[k]的映射,令f(v)表示与顶点v关联的边的颜色的加和.如果对任意一条边uv∈E(G),都有φ(u)≠φ(v),f(u)≠f(v),则称φ为图G的邻和可区别[k]-边染色,k的最小值称为图G的邻和可区别边色数,记为ndi_Σ(G).若对任意一条边uv∈E(G),都有f(u)≠f(v),则称φ为图G的k-边权点染色,称图G是k-边权可染的.运用组合零点定理证明了对于最大度不等于4的Halin图有:ndi_∑(G)≤Δ(G)+2,并证明了任一Halin图是4-边权可染的.     

Pkn(k≡2(mod 3))的邻点可区别的强全染色

对简单图G(V,E),V(Gk)=V(G),E(Gk)＝E(G)U{uv|d(u,v)=k},称Gk为G的k次方图,其中d(u,v)表示u,v在G中的距离.设f为用k色时G的正常全染色法,对 uv∈E(G),满足C(u)≠C(v),其中C(u)＝{f(u)}U{f(v)|uv∈E(G)}U{f(uv)|uv∈E(G)},则称f为G的k邻点可区别的强全染色法,简记作k-ASVDTC,且称Xast(G)＝min{k|k-ASVDTC ofG}为G的邻点可区别的强全色数.本文得到了k≡2(mod 3)时的Xast(Pkn),其中Pn为n阶路.     

Two-tree的调和指标

图G的调和指标是指图G中所有边uv所对应的2/d(u)+d(v)权和,其中d(u),d(v)分别表示顶点u,v的度数.本文的主要目标是计算出所有的n个顶点的two-tree图中的最小与第二小的调和指标.     

若干图的强染色

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

半无爪可迹图的度和条件

可迹图即为一个含有Hamilton路的图.令$N[v]=N(v)\cup\{v\}$, $J(u,v)=\{w\in N(u)\cap N(v):N(w)\subseteq N[u]\cup N[v]\}$.若图中任意距离为2的两点$u,v$满足$J(u,v)\neq \emptyset$,则称该图为半无爪图.令$\sigma_{k}(G)=\min\{\sum_{v\in S}d(v):S$为$G$中含有$k$个点的独立集\},其中$d(v)$表示图$G$中顶点$v$的度.本论文证明了若图$G$为一个阶数为$n$的连通半无爪图,且$\sigma_{3}(G)\geq {n-2}$,则图$G$为可迹图; 文中给出一个图例,说明上述结果中的界是下确界; 此外,我们证明了若图$G$为一个阶数为$n$的连通半无爪图,且$\sigma_{2}(G)\geq \frac{2({n-2})}{3}$,则该图为可迹图.     

糙度和k—覆盖图

一、引言 我们所考虑的图是指没有环和重边的有限无向图。在本文中未加说明的定义和记号请参见文献[2]。设G是一个具有顶点集V(G)和边集E(G)的图。对V(G)的一个子集S,用G[S]表示G的由S导出的子图且令G—S=G[V(G)\S]。若G[S]不含边,则称S为独立集。我们用d_G(x)表示G中顶点x的次数,用Γ_G(x)表示G中与顶点x邻接的顶点集合。对令.我们分别用△(G)和ω(G)表示G的顶点的最大次数和连通分支数。若对任意的且ω(G—S)>1有     

关于图P_n~k的均匀染色

对简单图G=〈V,E〉及自然数k,令V(Gk) =V(G) ,E(Gk) =E(G)∪{uv|d(u,v) =k},其中d(u,v)表示G中u,v的距离,称图Gk为G的k方图.本文讨论了路的k方图Pkn的均匀点染色、均匀边染色和均匀邻强边染色,利用图的色数的基本性质和构造染色函数的方法,得到相应的色数χev(Pkn) ,χ′ee(Pkn) ,χ′eas(Pkn) .并证明猜想“若图G有m -EASC,则一定有m +1 -EASC”对Pkn是正确的.     

两类图的L(2.1)-标号数

图G的一个L(2.1)-标号是从顶点集V(G)到非负整数的一个函数f,使得若d(u,v)=1时,有|f(u)-f(v)|≥2;若d(u,v)=2时,有|f(u)-f(v)|≥1.图G的L(2.1)-标号数λ(G)是G的所有L(2.1)-标号下的跨度max{f(v):v∈V(G)}的最小数.图Fn+1*为扇图的路上每个顶点增加一个悬挂边得到的图.图Hn为轮图的圈上每个顶点增加一个悬挂边得到的图.本文确定了图Fn+1*与Hn的L(2.1)-标号数.     

序贯可加图的结构

给定一个(p,q)图G和一个正整数k，G的一个k序贯可加性编码是不同的数k,k+1,…,k+p+q-1到G的p+q个元素的一种分配，使得G的每一边e=uv得到分配给顶点u和v的数值之和。若图的元素容许有这样的一种分配，则称该图是一个k序贯可加图。该文将给出序贯可加图的若干结构性质，并构造一个k序贯可加图的无限簇。      

关于图 G_Δ的圈秩较小时的边色数分类

设 G 是简单连通图,由 Vizing 定理知,△(G)≤x′(G)≤△(G)+1,其中△(G)表示图 G 的最大顶点次,x′(G)是 G 的边色数.若 x′(G)=△(G),则称 G 为第一类图,记为 G∈C~1;否则称 G 为第二类图,记为 G∈C~2.其它图论术语及记号均与[1]一致.令 F={u|d(u)=△(G),u∈y(G)},记 GΔ=G[F].一条边 e(或顶点 v)称     

边覆盖临界图的一些性质

设G是一个简单图,其顶点集为V(G)而边集为E(G),S∈E(G)称为 G的一个覆盖,如果由S导出的子图为G的一个生成子图. G的边覆盖色数χ'c(G)是E(G,)所能划分成的最大边覆盖数.已知δ-1 ≤χ'c(G)≤δ,由此将χ'c(G)=δ的图称为CI类图,否则称为CII类图.若G是连通CII类图,且G不是完全图,对任意的u,u∈V(G),e=uv( )E(G),都有χ'c(G+e)＞χ'c(G)成立,则称G为边覆盖临界的.本文研究了边覆盖临界图的一些性质.即若G为边覆盖临界图,则对任意的u,v∈V(G),若e=uv( )E(G),总存在w∈{u,v},有d(w)≤2δ-2,且w至少与max{d(w)-δ+1,3d(w)-4δ+4}个最小度顶点相邻.     

围长至少为5的平面图的injective-染色

图G的injective k-染色是指映射c:V(G)→{1,2,…,k},使有公共邻点的两个顶点u,v满足c(u)≠c(v),用X_i(G)表示使G有一个injective k-染色的最小正整数k.对g(G)≥5的平面图G,若△(G)≥20,证明了X_i(G)≤△+3.     

长圈的邻域交条件的推广

证明了若G为一个k(k≥2)连通简单图,独立数为α,V(G)=n≥3,X1,X2,…,Xk是顶点集合V的子集,X=X1∪X2∪…∪Xk,且对于Xi(i=1,2,…,k)中任意两个不相邻点u,v,|N(u)∩N(v)|≥α,则X在G中可圈,并给出几个相关推论.     

关于P_n~3的优美性(英文)

设G(V,E)是一个简单图,对自然数k,当V(G~k)=V(G,E(G~k)=E(G)∪{uv|d(u,v)=k},则称图G~k为k-次方图,本文证明了图P_n~3的优美性。