关于图 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为简单连通图,由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,令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.     

围长至少为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是一个简单图,其顶点集为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}个最小度顶点相邻.     

mC4的顶点被多重色集合可区别的一般边染色北大核心CSCD

简单图G的一个一般边染色是指若干种颜色关于图G的所有边的一个分配,不要求相邻的边被分配不同的颜色.设f是G的使用了k种颜色的一般边染色,若对(?)u,v∈V(G),u≠v,都有与u关联的边的颜色构成的多重集合异于与v关联的边的颜色构成的多重集合,那么称f是使用了k种颜色的顶点被多重色集合可区别的一般边染色.对G进行顶点被多重色集合可区别的一般边染色所需的最少颜色数记为c(G),并且称c(G)为图G的顶点被多重色集合可区别的一般边色数.本文确定了m个C_4的点不交的并mC_4的顶点被多重色集合可区别的一般边色数.     

D(2)-点可区别正常边色数的一个上界

图G的D(β)-点可区别正常边染色是指G的一个正常边染色f使得对任意两点u,v∈V(G),0相似文献   

独立集的度和与图的哈密尔顿性

关于哈密尔顿连通图的一个基本结果是Ore给出的：设G是n阶图,若对于任意两个不相邻顶点u和v,有d(u) d(v)≥n 1,则G是哈密尔顿连通的．设G是一个图,对于任意u (?)V(G),令N(U)=∪_(u∈∪)N(u),d(U)=|N(U)|,称d(U)是U的度．本文利用独立集的度和得到如下结果：设s和t是正整数,G是(2s 2t 1)-连通n阶图．若对于任两个强不交独立集S,T,|S|=s,|T|=t,有d(S) d(T)≥n 1．则G是哈密尔顿连通的．同时也得到图的哈密尔顿性的其它相关结果．两个独立集S和T称为强不交的,如果S∪T也是独立集．     

两类图的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)-标号数.     

一个定理的简单证明

本文对文献[1]的部分结论给出了一个很简单的证明。本文讨论的图是无向简单图。用d_G(v)或者d(v)表示图G中顶点v的次或度。用G[U]表示点集U的导出子图。其余符号见[2]。设G是一个图,|V(G)|=p,若k是给定的非负整数,若对图G中每一对不相邻的顶点u和v,都有d(u) d(v)≥p k,则称图G为Ore-k型图。     

若干图的强染色

图 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的任意边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)是哈密顿的.     

一个关于余直径的度条件

本文研究关于余直径的度条件,主要结果是,若G是3-连通图,其顶点集为V(G)={v1,v2,…,vn),其度序列为: d(v1)≤d(v2)≤…≤d(vn)则对G的任意一条边e都存在特征点对va,vb,使G中过e的最长圈至少为d(va)+d(vb)-1.在相同的条件下我们有d*(G)≥ m-2,     

一类直径为2的极大平面图的Mostar指数

图G的Mostar指数定义为Mo(G)=∑uv∈Ε(G)|nu-nv|,其中nu表示在G中到顶点u的距离比到顶点v的距离近的顶点个数,nv表示到顶点v的距离比到顶点u的距离近的顶点个数.若一个图G的任两点之间的距离至多为2,且不是完全图,则称G是一个直径为2的图.已知直径为2点数至少为4的极大平面图的最小度为3或4.本文研究了直径为2且最小度为4的极大平面图的Mostar指数.具体说,若G是一个点数为n,直径为2,最小度为4的极大平面图,则(1)当n≤12时,Mostar指数被完全确定;(2)当n≥13时,4/3n2-44/3n+94/3≤Mo(G)≤2n2-16n+24,且达到上,下界的极图同时被找到.     

图的部分控制集问题的修正 Greedy算法

部分控制集问题是对于给定的顶点赋权图G=(V,E;c)和正整数K,寻找图G一个顶点子集T,使得在其控制下的顶点个数不小于K且T中顶点权和达到最小。本文讨论了部分控制集问题的NP-困难性;给出了该问题的一种修正Greedy近似算法,并对其近似度H(K)给出了证明。     

边色数分类的两个充要条件

设图 G 是简单连通图,从 Vizing 定理可知:Δ(G)≤x′(G)≤Δ(G) 1,其中Δ(G)表示图 G 的最大顶点次,x(G)是图 G 的边色数.若 x′(G)=Δ(G),则称 G 为第一类图,并简记为 G∈C~1;否则称 G 为第二类图并简记为 G∈C~2;本文的目的在于讨论边色数分类问题.     

连通图中过指定顶点集的圈的存在性

图论中的一个重要问题是Hamilton圈的存在性问题.由于一般的Hamilton图的充要条件难于获得,故一些作者便退一步在某些给定类型的图中寻求长度尽可能大的圈.例如,Dirac即证明了2-连通图中存在着经过某一指定顶点集N(u)UN(v)U{u,v}的圈,从而得到了如下的定理(可参看[3]的介绍): 定理A.设G是个n阶的2-连通图,P是G中的一条最长路,u及v是P的两端点,d(u)+d(v)=f.若4≤f相似文献   

边色数分类的两个结果

设图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;A.J.W.Hilton提出了如下猜想[1]:如果G是简单图,且满足:(ⅰ)△(G)>2/3(|V(G)|-3),(ⅱ)δ(G_△)≤1。则G∈C~1。本文的目的是围绕着这一猜想,得出了两     

平面图最小平衡二部划分的上界

关于平面图的平衡二部子图的研究有一个猜想:任意一n个顶点的平面图G(V,E),必含有一个平衡二部子图G(V_1,V_2)使得e(V_1,V_2)≤n.证明了若n个顶点的哈密尔顿平面图G(V,E)中含有一个近似等边三角形,n≥18,那么G(V,E)必含有一个平衡二部子图G(V_1,V_2)使得e(V_1,V_2)≤n.     

图的Hyper-Wiener指数的综述(英文)

设G是一个图.G的顶点u和v的距离是u和v之间最短路的长度.Wiener指数是G中所有无序顶点对之间距离之和,而Hyper-Wiener指数定义为WW(G)=?∑u,v∈V(G)d(u,v)+?∑u,v∈V(G)d2(u,v),式中的和取遍G的所有顶点对.本文总结了图的Hyper-Wiener指数的最近结论.