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

边覆盖临界图的一些性质

设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}个最小度顶点相邻.     

第一类图的若干充分性条件

1964年,V.G.Vizing[2]证明了简单图 G 的边色数 x′(G)满足△(G)≤x′(G)≤△(G)+1.其中△(G)为图 G 的最大度.若x′(G)=△(G),则称 G 为第一类图,并简记为 G∈C~1;若 x′(G)=△(G)+1 则称 G 为第二类图,并简记为 G∈C~2.     

关于梅花图的优美性

<正> 对于一个简单图 G=(V,E),若对每一个 v∈V,存在一个整数 l(v)(称为顶点 v的标号)使满足:(1)(?)u,v∈V,若 u≠v,,则 l(u)≠l(v);(2)max{l(v)|v∈V}=|E|;(3)(?)e′,e″∈E,若 e′≠e″,则 l′(e′)≠l′(e″),这里 l′(e)定义为|l(u)-l(v)|,此时若 e=uv,则称 G 为优美图(graceful graph).     

扩充竞赛图的(1,2)步竞争图

2011年Factor等人提出了有向图的(1,2)步竞争图的概念,并完全刻画了竞赛图的(1,2)步竞争图.设D=(V,A)是一个有向图.如果无向图G=(V,E)满足,V(G)=V(D)并且xy∈E(G)当且仅当D中存在顶点z≠x,y使得d_(D-y)(x,z)=1,d_(D-x)(y,z)≤2或者d_(D-x)(y,z)=1,d_(D-y)(x,z)≤2,那么称G为D的(1,2)步竞争图,记为C_(1,2)(D).本文主要刻画了扩充竞赛图的(1,2)步竞争图.     

关于齿轮图的优美性

对于一个简单图 G=(V,E),若对每一个 v∈V,存在一个整数 l(v)(称为顶点 v 的标号)使满足:(a)(?)u,v∈V,若 u≠v,则 l(u)≠l(v);(b)max{l(v)|v∈V}=|E|;(c)(?)e′,e″∈E,若 e′≠e″,则 l′(e′)≠l′(e″),这儿 l′(e)定义为|l(u)-l(v)|,若e=uv,则称 G 为优美图 (graceful graph).在文献[1]中,C.Hoede 指出了所有的轮都是优美图.本文将证明在轮图的轮圈上每相邻两顶点之间加入一点后所得的图亦为优美图.     

竖梯的局部替换图的L(d,1,1)-标号

图的L(d,1,1)-标号定义为顶点集V(G)到非负整数集的映射f,且当d(u,v)=1时,均有|f(u)-f(v)|≥d,当d(u,v)=2,3时,均有|f(u)-f(v)|≥1.不妨设0为最小标号,则称图G的所有L(d,1,1)-标号中的最大跨度max{f(v):v∈V(G)}的最小数为图的L(d,1,1)-标号数,记为λ_d(G).基本给出了竖梯的局部替换图的L(d,1,1)-标号数的确切值或界.     

图加一条边后的带宽和

令$BS(G,f)=\sum\limits_{uv\in E(G)}|f(u)-f(v)|$, 其中$f$为$V(G)\rightarrow\{1,2,\cdots,|V(G)|\}$的双射, 并称$BS(G)=\min\limits_{f}BS(G,f)$为图$G$的带宽和. 讨论顶点数为$n$的简单图$G$加上一条边$e\in\overline{E(G)}$后, 带宽和$BS(G+e)$与$BS(G)$的关系, 得其关系式$BS(G)+1\leq BS(G+e)\leq BS(G)+n-1$. 并证明此不等式中等号可取到, 即存在图$G_{1}$和$G_{2}$使得$BS(G_{1}+e)=BS(G_{1})+1$, $BS(G_{2}+e)=BS(G_{2})+n-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的点集的最大顶点数.     

最大度不大于5的Halin-图的点强全染色

图G(V,E)的一正常k-全染色f称为G(V,E)的一k-点强全染色当且仅当任意( A)v∈V(G),N[v]中的元素染不同色,其中N[v]={u|uv∈V(G)}U{v},并且XusT(G)=min{k|存在G的k-点强全染色}称为G(V,E)的点强全色数.本文得到了△(G)≤5的Halin-图G(V.E)的XusT(G),并提出如下猜想设G(V,E)为每一连通分支的阶数不小于6的图,则XusT(G)≤△(G)+2,其中△(G)表示图G的最大度.     

消去图、覆盖图和均匀图的若干结果

设 G是一个图 ,g,f是定义在图 G的顶点集上的两个整数值函数 ,且g≤f.图 G的一个 ( g,f) -因子是 G的一个支撑子图 F,使对任意的 x∈V( F)有g( x)≤ d F( x)≤ f ( x) .文中推广了 ( g,f) -消去图、( g,f ) -覆盖图和 ( g,f) -均匀图的概念 ,给出了在 g相似文献   

图的1-因子、f-因子和(g,f)-因子

设G是一个图且有一个1-因子F,g和f是定义在V（G）上的非负整数值函数且对每个X∈V(G)有g（X）＜f(X)≤dG（x）,且f(v(G))为偶数．（i）若对每个xy∈F有f(x)=f(y)且G－{x,y}有一个（g,f)-因子,则G有一个（g,f)-因子;（ii）若对每个xy∈F有f(X）=f（y）且G-{X,y}有f-因子,则G有f-因子.     

图的邻接矩阵的行列式与积和式的递推表达式

设A(G)是简单图G的邻接矩阵,H是由G的独立边和不交圈组成的生成子图的集合,e是H中某个图的独立边,C是H中图的圈,且e∈E(C).记G-e是G的删边子图,G\W是从G中删去导出子图W中的顶点及其关联边后得到的图.那么A(G)的行列式为detA(G)=detA(G-e)-detA(G\e)-2(-1)~(|V(C)|)detA(G\C)A(G)的积和式为perA(G)=perA(G-e)+perA(G\e)+2perA(G\C)这里,C取遍H中图的经过边e的圈.     

完全二部图K_(1,n),K_(2,n)和K_(3,n)的点强可区别全染色

设f是图G的一个正常全染色.对任意x∈V(G),令C(x)表示与点x相关联或相邻的元素的颜色以及点x的颜色所构成的集合.若对任意u,v∈V(G),u≠v,有C(u)≠C(v),则称.f是图G的一个点强可区别全染色,对一个图G进行点强可区别全染色所需的最少的颜色的数目称为G的点强可区别全色数,记为X_(vst)(G).讨论了完全二部图K_(1,n),K_(2,n)和L_(3,n)的点强可区别全色数,利用组合分析法,得到了当n≥3时,X_(vst)(K_(1,n)=n+1,当n≥4时,X_(vst)(K_(2,n)=n+2,当n≥5时,X_(vst)(K_(3,n))=n+2.     

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-边权可染的.     

关于图的符号星控制数

设G=(V,E)是一个图,u∈V,则E(u)表示u点所关联的边集.一个函数f:E→{-1,1}如果满足■f(e)≥1对任意v∈V成立,则称f为图G的一个符号星控制函数,图G的符号星控制数定义为γ'_(ss)(G)=min{■f(e):f为图G的一个符号星控制函数}.给出了几类特殊图的符号星控制数,主要包含完全图,正则偶图和完全二部图.     

直径为4的树的奇强协调性

对简单图G=〈V,E〉,如果存在一个映射f:V→{0,1,2,…,2 E-1}满足1)对任意的u,v∈V,若u≠v,则f(u)≠f(v);2)对任意的e1,e2∈E,若e1≠e2,则g(e1)≠g(e2),此处g(e)=f(u)+f(v),e=uv;3){g(e)e∈E}={1,3,5,…,2 E-1},则称G为奇强协调图,f称为G的奇强协调标号.给出了直径为4的树的奇强协调标号.     

图的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指数的最近结论.