两类联图的全着色

一个图Ｇ＝（Ｖ，Ｅ）的一个Ｋ－全着色是从Ｖ∪Ｅ到Ｉ＿Ｋ＝｛１，２…Ｋ｝上的一个映射ψ；如果对Ｖ∪Ｅ中任意两个相邻或相关联的元素ｅ＿１，ｅ＿２，都有ψ（ｅ＿１）≠（ｅ＿２）时，则称ψ为Ｇ的一个正规全着色。图Ｇ的全色数定义为Ｘ＿ｒ（Ｇ）＝ｍｉｎ｛Ｋ｜存在Ｇ的一个正规ｋ－全着色｝。令Ｃ＿ｎ为ｎ个点的圈，为ｍ个点的独立集，Δ为图的最大度。本文证明了在ｍ≠ｎ时联图Ｃ＿ｍ＋Ｃ＿ｎ的全色数为Δ＋１；在ｍ＋２＜ｎ或ｍ＞ｎ时，联图＋Ｇ＿ｎ的全色数也为Δ＋１。     

几族全着色临界图

本文引进全着色矩阵的概念,每个全着色矩阵确定一个简单图及其一全着色。若图G的全色数为k,G的任一真子图的全色数均小于k,称G为k-全着色临界图。对任意奇数r>3,我们给出若干阶数最小的非平凡r~-全着色临界图。     

圈与偶图的笛卡尔积图的邻点可区别全染色

利用图的结构性质,研究了圈与偶图的笛卡尔积图的邻点可区别全染色,得到了邻点可区别全色数.     

几类循环图的分数染色数

通过构造几类图的最大独立集,给出了它们的分数染色数的下界;再通过构造具有该下界值的分数染色,给出了这几类循环图的分数染色数的上界,于是就确定了它们的分数染色数.     

图的控制临界数

引入了图的控制临界数的概念:图的控制临界数等于使它的控制数减小而需添加的最少边数。给出了一般图的控制临界数的最好上界;并确定了路、圏和完全多部图的控制临界数的精确值。     

一类团横贯数等于团独立数的图

把图G的每一个团看作一个点，两点之间有边相连当且仅当它们对应的团有非空交（即有公共点）．这样得到的图称为图G的团图，记为K（G）．文章证明了如果一个图对应的团图为二部图，则该图的团横贯数等于团独立数，即τc（G）=ac（G），另外给出了判断一个图的团图是否为二部图的一个计算时间为o（n^4）的多项式时间算法．     

Halin图的均匀染色

Halin图是最小度不小于3的3－连通平面图,且存在一个面,删除关联于该面的所有边后是一棵树。称图G为均匀k-可着色的,如G的顶点集V可分划成K个独立集V1、V2、…Vk,使||Vi|-|Vj||≤1（0≤i＜j≤k）;称使图G的均匀k-可着色的最小整数k为G的均匀色数,记为xe（G）。本文对非K4的Halin图证明△（G）≠4时,对任意的整数k≥［△（G）／2]＋1;当△（G）＝4时,对任意整数的k≥4,G是均匀k-可着色的。从而对Halin图证明了均匀染色猜想（ECC）。     

高度不正则图的全着色

图Ｇ的正常ｋ全着色是指用ｋ种颜色对Ｇ的点和边着色，使相邻或相关联的元素（点或边）着不同色。其中最小的ｋ称为Ｇ的全色数，记为χＴ（Ｇ）。设Ｇ是一个简单图，υ是Ｇ的任意一个顶点，若与υ相邻的顶点的度互不相同，则称Ｇ为高度不正则图。对高度不正则图Ｇ，文中证明了χＴ（Ｇ）＝Δ（Ｇ）＋１，同时也给出了着色的算法，其中Δ（Ｇ）为Ｇ的最大度数且Δ（Ｇ）≥２。     

一类含星S3之粘接图S3⊙G的niche数

星S3＝K1,3是无穷niche图.但是本文通过星S3与几个简单图类之粘接图的niche数以及星与一般图之粘接图的niche数等问题的研究表明:许多粘接图S3⊙G都是有限niche图.     

轮和完全等二部图联图的若干染色问题

图的染色理论是图论的一个重要分支。本文使用分析的方法得到了轮和完全等二部图联图的全色数、均匀全色数和邻点可区别边色数。     

正则k-覆盖图

图G的k-正则生成子图称为G的一个k-因子,若图G的每条边都含于G的一个k-因子中,称图G足k-覆盖的。对任意给定的正整数γ、λ和k(λ≥2),基于文[1,2]的已知结论,本文给出了所有γ-正则λ-边连通图是k-覆盖图的充分必要条件。     

连通图生成树的叶子数

图G的一度点称为G的叶子．证明了对G的生成树的叶子数最小值到G的生成树的叶子数的最大值之间的任何整数，G都有某个生成树的叶子数等于这个值．     

正整数的连续奇偶拆分

正整数n的一个拆分是指将n表示为一个或多个正整数的无序和。n的不同拆分方式数称为n的拆分数。给出了一个正整数n能拆分成连续奇数和连续偶数之和的充要条件,并求出了这两种拆分的拆分数。将其结果用于讨论不定方程x2?y2=n,给出了判断该方程解的存在性条件,以及解的个数的确定。证明了如果n能表示成连续奇数和连续偶数之和,则表示法唯一。     

关于乘积图的导出匹配划分数

图G的导出匹配划分数是图论中研究的热点问题.针对乘积图的导出匹配划分数进行了研究,给出了乘积图的导出匹配划分数的一个下界和一个上界,对一些特殊图类的乘积图,还给出了其导出匹配划分数的精确结果,可为相关研究参考.     

D和H与介质无关的充要条件的研究

用电磁学方法通俗地证明了电位移矢量Ｄ 和磁场强度矢量Ｈ 与介质存在无关的充要条件     

圆色数在若干图运算下的不变性

研究了圆色数在一些图运算下的不变性,并利用这些图运算：由已知圆色数为r=kd的图,构造出若干类圆色数为r的图。从一个已知圆色数为r的图（如Gkd）,分别借助于图的单一顶点合并、双重顶点合并以及笛卡尔积3种运算,得到了3类圆色数为r的图。     

对一类最小图的研究

对一个与并行结构和通信网络设计密切相关的图论公开性问题进行了研究。讨论了图的结点数为n,连通度至少为k,k-直径至多为d的条件下的最小图问题,给出了一般条件下最小图边数条数的上、下界,在此基础上,得到了两种条件下最小图边数的计算公式,结合已有的图论结果,对文中所提到的最小图进行了构造。