Halin图的2-距离和可区别全染色

记[k]={1,2,…,k}为颜色集.设f:V(G)∪E(G)→[k]为图G的一个k-全染色.令S(u)=f(u)+∑/_(v)∈N_(G)(u)f(uv),其中,N_(G)(u)表示u的邻点集.若对G中距离不超过2的任意两点u、v,有S(u)≠S(v),则称f为图G的一个2-距离和可区别k-全染色.图G的2-距离和可区别k-全染色中最小k值称为图G的2-距离和可区别全色数,记为χ″_(2-Σ)(G).该文运用组合零点定理证明了最大度至少为4的Halin图G满足χ″_(2-Σ)(G)≤max{Δ(G)+2,9},其中,Δ(G)表示图G的最大度.

Halin图的Alon-Tarsi数

图G的Alon-Tarsi数,是指最小的k使得G存在一个最大出度不大于k-1的定向D满足G的奇支撑欧拉子图的个数不同于偶支撑欧拉子图的个数.通过分析Halin图的结构,利用Alon-Tarsi定向的方法确定了Halin图的Alon-Tarsi数.

Halin图的有点面约束的边染色

研究了Halin图的有点面约束的边染色,给出了Halin图的有点面约束的边染色色数的一个精确结果.

关于几类图的L(2,1)标号问题(英文)

图G的L( 2 ,1 )标号是一个从顶点集V(G)到非负整数集的函数f(x) ,使得若d(x ,y) =1 ,则｜f(x) -f(y) ｜≥ 2 ;若d(x ,y) =2 ,则｜f(x) -f(y) ｜≥ 1 .图G的L( 2 ,1 ) 标号数λ(G)是使得G有max{f(v) ∶v∈V(G) }=k的L( 2 ,1 )标号中的最小数k .Griggs和Yeh猜想对最大度为Δ的一般图G ,有λ(G) ≤Δ2 .本文给出了Kneser图 ,Mycieklski图 ,Descartes图 ,Halin图的λ值的上界 。

伪Halin-图的无循环边着色

图G的无循环边着色是指图G的正常的边着色且任意的圈上不着双色.图G的无循环边色数是指对G进行无循环边着色所需的最少色数k,记为a′(G).给出了伪Halin图的无循环边色数满足猜想a′(G)Δ(G)+2,并且对任意的伪Halin图G且G≠K4,有a′(G)=Δ(G).

Δ(G)=3时的Halin图的边面全色数

研究３正则Ｈａｌｉｎ 图的边面全色数问题，证明了《最大度Δ（ Ｈｇ） ≥７ 及Δ（ Ｈｇ）＝ ４，５ ，６ 的Ｈａｌｉｎ 图的边面全色数》一文提出的如下猜想成立：对Δ（ Ｇ） ＝ ３ 时的Ｈａｌｉｎ 图有４ ≤χｅｆ（Ｇ） ≤５ ，这里Δ（ Ｇ） 表示图Ｇ 的最大度数，χｅｆ表示图Ｇ的边面全色数。

外平面图和Halin图谱半径的上界

本文给出了平面图中的外平面图的谱半径的上界，ρ（Ｇ）≤３／２＋．改进了１９９３年，ＣａｏＤａｓｏｎｇ和 Ｖｉｎｃｅ Ａ关于外平面图的谱半径上界；然后给出了 Ｈａｌｉｎ图的谱半径的可达上界，并刻划了达到上界的极图 ρ（Ｇ）≤１＋，等式成立当且仅当 Ｇ≌ Ｗｎ（轮图）．

Halin图谱半径的新上界及极图

利用移接变形的方法再结合特征值的计算技巧刻画出Halin图中谱半径达到第二大的极图,从而得到除轮图以外的Halin图的谱半径的上界以及极图.

Halin图的无圈边着色

设f是图G的一个正常边着色,若在f下G中没有2-色圈,则称f是图G的一个无圈边着色,其所用最小色数为G的无圈边色数。N．Alon猜想对所有简单图,无圈边色数不超过其最大度加2。本文证明了该猜想对Halin图成立,且当△≤4时,其色数不超过5；当△≥5时,其色数等于最大度。

△(G)≥6的Halin图的点强全染色

图G(V,E)的正常k-全染色σ称为G(V,E)的k-点强全染色当且仅当v∈VG,Nv中的元素染不同色,其中Nv=u｜uv∈EG∪v,xTvsG=mink│存在G的k-点强全染色称为G(V,E)的点强全色数。本文证明了:对于△G≥6的Halin图G(V,E),有xTvsG≤△G+2,其△G表示图G的最大度。

最大度△(Hg)≥7及△(Hg)=4、5、6的Halin图的边面全色数

本文证明了△(Hg)≥7及△(Hg)=4、5、6时,Halin图Hg的边面全色数。其中△(Hg)表示Halin图的最大度。

Halin图中的Hamilton路径

本文证明了所有的Halin图都是Hamilton连通的。并给出反例,说明Halin图中存在两条独立边不包含在任何Hamilton圈中。

关于几类图的L(3,2,1)-标号问题

图G的L(2 ,1 )_标号是一个从顶点集V(G)到非负整数集的函数f(x) ,使得若d(x ,y) =1 ,则|f(x) -f(y) |≥ 2 ;若d(x ,y) =2 ,则 |f(x) -f(y) |≥ 1 .图G的L(2 ,1 )_标号数λ(G)是使得G有max{f(v) :v∈V(G) } =k的L(2 ,1 )_标号中的最小数k.该文将L(2 ,1 )_标号问题推广到更一般的情形即L(3,2 ,1 )_标号问题 ,并得出了Kneser图、高度不正则图、Halin图的λ3(G)

Halin图的色性

本文证明了：对Ｈａｌｉｎ图Ｇ，（ｉ）χ（Ｇ）＝４当且仅当ｇ为偶阶轮图；（ｉｉ）χ′（Ｇ）＝△；（ｉｉｉ）对△（Ｇ）≥５，有χＴ（Ｇ）＝△＋１。这里χ（Ｇ）、χ′（Ｇ）及χＴ（Ｇ）分别表示Ｇ的色数、边色数及全色数。

若干图的强染色(英文)

图 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)= 4,5,6时的Halin图的边面全色数

本文证明了：对△（Ｇ）＝４，５，６时的Halin图Ｇ，有Xef（Ｇ）≤６。这里Xef（Ｇ）表示图Ｇ的边面全色数，△（Ｇ）表示图Ｇ的最大度数。

关于Halin图染色方面的一些结果

简述Halin图的着色方面的一些结果 ,并证明了 3 正则Halin图的点边全色数 4≤χT(G)≤

Halin图的均匀边染色

图G的一种均匀k 边染色是指用k种颜色去染G的边使得对G的每一个顶点v ,任何两种颜色染与v相关联边的数目最多相差 1.证明了对任意的大于 3的整数k,Halin图都有均匀k 边染色 ;

3-正则Halin图的可区别数

根据3-正则Halin图的Hamilton性,结合其顶点间距离的关系,通过适当地选取顶点进行着色后得证了4和6阶以上3-正则Halin图G的可区别数分别为3和2.

Halin图谱半径的进一步论述

束金龙等给出了n阶Halin图的谱半径满足不等式ρ(Gn)≤1+n-2a+2.讨论了该不等式取得等号的充要条件,并且讨论了含有2个内点的Halin图的谱半径,得到了含有2个内点的Halin图的谱半径单调递增的结论.