外部平面图的平方图的染色

图G的平方图，记作G^2，是一个以原图的顶点集为顶点集，若原图中两点的距离不大于2则连以边所成的图．本文确定了圈的平方图的色数．对于外部平面图，得到以下结论：设G是一个最大度为△(G)的简单连通外部平面图，G≠C5．则x(G^2)≤△(G) 2．     

2-连通外部平面图的平方图的列表染色

图G的平方图,记作G2,是一个以原图的顶点集作为顶点集,若原图中两点的距离不大于2则连以边所成的图.图G的列表染色数,记作lχ(G),定义为最小的自然数k,使得满足:对任一顶点给定k种颜色的列表,且染色时每个顶点的颜色只能从自身的颜色列表中选择时,总存在G顶点的一个正常染色.设G是一个最大度为Δ(G)的2-连通外部平面图,则lχ(G2)≤Δ(G)+2.     

不含3圈和4圈的1-平面图是5-可染的

若图G能画到平面上,且允许每条边至多出现一个交叉点,则图G是1-平面图。图G的一个正常点染色是指存在一个顶点集到颜色集的映射φ:V(G)→{1,2,…,k},对于G中的任意两个相邻的点u和v,φ(u)≠φ(v)。图G的一个k染色是指图G能够正常点染色所需的色数至少为k,图G有一个k染色又称图G是k-可染的。通过权转移的方法证明了不含3圈和4圈的1-平面图是5-可染的。     

几类平面图的集合色数

设G是非平凡连通图,记c:V(G)→N是G的一个顶点染色,这里相邻的两个顶点可以着相同的颜色。对于图G的任一顶点ν,与ν相邻的顶点所着颜色的集称为邻色集,记NC(ν)。如果G中任意相邻的两个顶点ν,u满足NC(u)≠NC(ν),则称c是G的一个集合染色。集合染色所需的最少的颜色数称为G的集合色数,记χs(G)。本文给出了团数是3的平面图,没有4圈的平面图及烟花图和风车图的集合色数。     

特殊平面图的集合色数

设G是非平凡连通图,记c:V(G)→N是G的一个顶点染色,这里相邻的两个顶点可以着相同的颜色。对于图G的任一顶点v,与v相邻的顶点所着颜色的集称为v的邻色集,记为NC(v)。如果G中任意相邻的两个顶点u,v满足NC(u)≠NC(v),则称c是G的一个集合染色。集合染色所需的最少的颜色数称为G的集合色数,记为χs(G)。本文给出了与轮图有关的一类平面图的集合色数,向日葵图和风车图的集合色数,最后给出了一个猜想。     

2-外平面图的L（2，1）-标号数

一个平面图被称为 2-外平面图,如果它能嵌入平面使得所有顶点出现在至多2个面的边界上.主要研究了2-外平面图的L(2,1)-标号,得到:若图G是一个2-外平面图,则λ(G)≤Δ(G)+12,其中Δ(G)表示G的最大度.     

图的(2,1)-点面标号

图G的一个k-(2,1)-点面标号是一个映射c:V(G)∪F(G)→{0,1,…,k},使得相邻的顶点取不同的值,相邻的面取得不同的值,相关联的点面取值至少相差2.G的(2,1)-全标号数λvf2(G)定义为G所有的k-(2,1)-点面标号中最小的k值.给出了树、圈、欧拉二部图、K4、外平面图等简单图类的(2,1)-点面标号数的上界,而且完全刻画了至多含有一个闭内面的外平面图的(2,1)-点面标号数.     

关于平面图点荫度的一点改进

一个非平凡图G的点荫度a(G)是一个最小图顶点划分数使得每一个划分集的导出子图是一个森林.近年来对点荫度的研究成为图论的一个焦点并且关于这个问题有更深一步的发展,例如,随机图的点荫度以分式点荫度等.得到一个关于平面图的点荫度的一个上界;如果平面图G是没有3-圈,或是没有4-圈,或是没有5-圈,那么G的点荫度不超过2.研究的起因是一个著名的猜想:任何3-可着色的平面图的点荫度不超过2.四色定理是图论中最著名的一个定理,伴随产生了一个问题,那就是什么样的平面图是3-可着色的.不幸,这是一个难问题,Garev等人证明了判定一个平面图是否3-可着的即使在一个点不超过4的条件下仍然是NP-难问题.因此这个猜想是一个不易解决的,人们开始在一些特殊图上进行验证这个猜想是否正确.我们知道一个著名的定理:不含3-圈的平面图是3-可着色的.结合结果,给出猜想的一个正面的肯定.Havel给出两个反例,如果平面图含有4-圈或有5-圈是不可3-可着色的,因此4-圈和5-圈在证明平面图是3-可着色时必须排除.不过在结论中,如果平面图不含有4-圈或不含有5-圈,那么它的点荫度不超过2.从而可以看出猜想的条件还是很强的.同时我们的结果也拓宽了张忠辅等人的结果:外平图的点荫度不超过2.     

平面图与对偶原理

该文利用对偶原理创造性地解决了平面图、连通图及对偶图之间的相互关系问题,纠正了长期以来对于平面图及其同构的错误认识,指出平面图必为连通图,平面图本质上是画在同一平面上的顶点、边、面均不相交的连通图。两个平面图的同构指这两个平面图的顶点、边、面之间均有一一对应关系。面是平面图区别于非平面图的本质特征。同构的平面图的对偶图必同构,事实上,平面图的对偶图是唯一的。任意一个平面图都伴有一个隐图,而该隐图实质上是该平面图的对偶图,该隐图可(根据对偶原理)通过D—过程画出。平面图与其对偶图互为对偶。显平面图与其隐对偶图合称为相伴对偶图。     

四正则哈密尔顿平面地图的数目(英文)

一个地图称为哈密尔顿的若其上的所有顶点都在一个圈上．若一个平面地图的所有顶点是四次的，且又是哈密尔顿地图，则称该平面地图为四正则哈密尔顿平面图一个地图是近四正则的，是指除去根点外，其余顶点的次均为四．本文提供了四正则哈密尔顿平面地图计数的一个公式和四正则平面地图计数的一个显式．     

一类整数距离图的点荫度

整数距离图以全体整数作为顶点集，顶点u、υ相邻当且仅当｜u-υ｜∈D，其中D是一个正整数集．对于m〉3，令Dm=[1,m]／[1,3]．本研究得到了G（Dm）的点荫度．     

一类哈密顿图的控制数的上界

设G=(V,E)是一个简单图,D是V的一个子集,如果集合V-D的任意点都与D中的点相邻,则称D为图G的一个控制集.图G的最小控制集中的点数称为G的控制数.本文对哈密顿图的控制数进行了研究,证明了命题:如果n阶图G是一个最小度为5的哈密顿图,则图G的控制数就不大于5n/14.     

双Cayley图的自同构群

设G是有限群，S是G的一个子集（可能含有单位元）。群G关于S的双Cayley图BCay(G,S)是以Gx｛0，1｝为点集而以｛｛（g,0），（sg,1）｝|g∈G,s∈S｝为边集的二部图。考查了双Cayley图BCay(G,S)的自同构群A，并决定了NA(Rι^r(G)）的结构。     

笛卡尔乘积图的k-路点覆盖

对于一个图G和一个正整数k,若图G中任意一条阶数为k的路都至少包含集合S⊆V(G)中的一个顶点,那么集合S就为图G的一个k-路点覆盖。最小的k-路点覆盖基数记为ψ_k(G),为图G的k-路点覆盖数。研究圈图分别与圈图、完全图及完全二部图做笛卡尔乘积图的k-路点覆盖,得到ψ_k(G)相关的精确值和上下界。     

给定控制数为2的图的谱半径的下界

一个图G(V,E)的控制数γ(G)是V的这样一个子集S的最小基数,使得G中每一个顶点或者在S中或者和S中的一些顶点邻接。本文讨论了控制数为2的n阶简单连通图的邻接谱半径下界,给出了谱半径达到最小时的极图。     

若干倍图的Smarandachely邻点边染色

图G(V,E)的Smarandachely邻点边色数是满足条件uv∈E(G),|C(u)＼C(v)|≥1并且|C(v)＼C(u)|≥1的一个正常边染色的最小边色数,其中C(u)=｛f(uv)|uv∈E(G)｝。给出了路、圈、星、扇图的倍图的Smarandachely邻点边色数。     

扇图的笛卡儿积的测地数(英文)

对于图G内的任意两点u和v,u-v测地线是指u和v之间的最短路.I(u,v)表示位于u-v测地线上所有点的集合,对于V(G)S,I(S)表示所有I(u,v)的并,这里u,v∈S.G的测地数g(G)是使I(S)=V(G)的点集S的最小基数.文章研究了Pm×Fn和Cm×Fn的测地数,这里Pm表示m阶路,Cm表示m阶圈,Fn表示n阶扇图。     

完全多部图和笛卡儿积图的线性点荫度

图的线性点荫度是对它的顶点进行染色所用的最少颜色数,同时使得染同一种颜色的点集所导出的子图,它的每个分支均为路．本文完全确定了完全多部图的线性点荫度,给出了笛卡儿积图的线性点荫度的一个上界,得到了一些特殊图（ 如路,圈和完全图） 的笛卡儿积图的线性点荫度．     

关于近似二部图边覆盖染色的一个充分条件

设G是一个简单图，其顶点集为V(G) 而边集为E(G) . S∈E(G)称为G 的一个边覆盖，如果由S 导出的子图是G 的一个生成子图. G 的边覆盖色数χ’c(G) 是E(G) 所能划分成的最大边覆盖数. 已知 δ-1≤χ’c(G)≤δ ，由此将 χ’c(G)=δ的图称为CⅠ类图，否则称为CⅡ类图. 显然，图的边覆盖染色分类问题是NP-完全的. 给出了近似二部图是CⅠ类图的一个充分条件，而且该条件中的下界是最好的。     

图的控制数及全控制数的估计

研究了图的控制数及全控制数，对满足一定条件的图给出了图的控制数及全控制数的估计。