条件染色正常图的几个充分条件

给定正整数r,图G的一个r-条件染色是G的顶点的一个正常染色,使得G中任意度数为d(v)的顶点v,其邻域中至少出现min{r,d(v)}种不同的颜色。若图的r-条件色数等于色数,则称图为r-正常的。给出了判断一个图G为正常图的一些充分条件,并用实例说明了这些条件并非必要的。     

全色数与小阶路的混合Ramsey数

以χ２（Ｇ）记一图Ｇ之全色数，Ｐｎ表ｎ阶路，混合Ｒａｍｓｅｙ数χ２（ｍ，Ｐｎ）为最小正整数ｐ，对于每个ｐ阶图Ｇ，或者χ２（Ｇ）≥ｍ，或者ＧＰｎ。当ｍ取任意正整数、ｎ≤４时，本文得到χ２（ｍ，Ｐｎ）的确值     

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

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

几类r-冠图的星边染色

图的星边染色是指图G的一个正常边染色使得G中没有长为4的路或圈是2-边染色的.图G的星边色数是指图G有星边染色的最小颜色数.本文中研究路、圈、扇、轮的r-冠图的星边染色问题.使用图分解法,反证法,染色构造法,组合分析法等方法和理论,得到4类r-冠图的星边色数.     

关于图的邻和可区别全染色的新方法

给出树的邻和可区别2-全染色方案,并结合三正则图最小消圈集的独立性以及消圈子图的无圈性,较为简洁地证明三正则图的邻和可区别全色数满足1-2猜想。进一步利用独立消圈集法确定r-正则图、Halin图以及路与路的笛卡尔乘积图的邻和可区别全色数。     

关于一类图的Hamilton路计数问题

研究了有向图的两个方面:竞赛图的Hamilton-路数的计数及有关竞赛排名的相关问题,多部或n-部竞赛图是完全n-部图的一个定向。根据Bongdy的强连通n-部竞赛图包含一个m-圈,其中m∈{3,4,…,n},Yeo的正则多部竞赛图是Hamilton图的原理,笔者在上述结论基础上,得到某些特殊的多部竞赛图的Hamilton路数的一些结论。     

关于一类联图的r-强边染色

单图G的r-强边染色是指图的距离不超过r的任意两点可区别的边染色，所谓两点u，v间的距离是指这两个点之间的最短路的长，记为d（u，v）．图G的r-强边色数x′s（G，r）表示．本文给出一类联图的2-强边色数的界，并将结论推广到r-强边色数的界．     

边染色图中的长彩色路问题

研究了边染色图中的彩色路,给出了满足一定色度条件下的边染色中彩色路的长度的下界。     

图K（r，2m）的邻点可区别全染色

在等完全r-部图全染色的研究中,首先确定了每部有2个点的完全r-部图的全色数;然后利用已得到的结果进一步研究每部有n个点的完全r-部图的全色数．采用上述思路研究了等完全卜部图的邻点可区别全染色,利用图分解的方法给出了每部有2个点的完全r-部图的邻点可区别全色数;并给出了每部有偶数个点的等完全r-部图的邻点可区别全色数．     

特殊图的条件染色

对于一个正整数r，图G的一个条件（k，r）-染色是使得图G的每个度至少为r的顶点至少与具有r种不同颜色的顶点相邻的正常的顶点染色．使图有一个条件（k，r）-染色的最小的整数k是图的第r个条件色数Z，（G），本文给出了对于不同的正整数，路、扇、轮的条件色数。     

图多彩染色中的2度点删除问题

对整数r0,图G的一个r-多彩染色是一个从顶点集V(G)到数集{1,2,…,k}的映射c,使得:(C1)相邻点获得的颜色不同;(C2)︱c(N(v))︱≥min{N(v),r}(其中N(v)代表v的邻点集)。使图G有一个正常的(k,r)-染色的最小k值称为G的多彩色数χ_r(G)。本文主要研究在图G中删掉任意一个2度点后多彩色数的变化。     

竞赛图中Hamilton路数的矩阵求法

任一对不同顶点都相邻且无2-圈的有向图称为竞赛图.每个竞赛图都有Hamilton路,利用矩阵方法可求得计算竞赛图中的Hamilton路及Hamilton路数的方法,既为计算竞赛图的Hamilton路及Hamilton路数增加了一种新的计算途径,还可用来计算任意有向图的所有长为k有向路.     

与泛圈图有关的一些结果

设r,t,j是正整数,对于n阶哈密顿图G,若对每一个r+tj+i(r+tj+i≤n),G中长为r+i+j的圈恰好有di个,0≤i≤t-1,其中t是di的周期,j是t重复的次数,则称图G为r-(d0,…, dt-1)-泛圈图.本文讨论了r-(3,3,4,3,4,3,3,3)-泛圈图,r-(3,5,5,3)-奇(偶)泛圈图,以及g(0,0,6,…,6)的界.     

高阶A-稳定和L-稳定的自开始单块混合法及其实现

对任何正整数r≥1,建立了收敛阶为(2r+1,2r+2,4r)的A-稳定自开始r-点单块混合法,也建立了收敛阶为(2r,2r+1,4r-1)的L-稳定自开始r-点单块混合法.这两个方法所导出的非线性方程组的维数是与之等价的2r-点单块法和2r-级(或2r+1级)R-K法的一半.还给出了它们的一种实现方案.     

图中含有给定圈的正则因子存在性度条件

设n和r是正整数使得r≥n＋1≥4．一个图被称为K1,n-free图，如果它不含导出子图K1,n。证明了：若G是一个有圈H的图且r｜V（G）｜为偶数，G—E（H）是连通的K1,n-free图且G—E（H）的顶点最小度至少是（n（r＋1）-3/r-2）[rn-2/2（n-1）]-n-1/r-2（[rn-2/2（n-1）]）^2＋n-3那么G有r-因子F包含H中的所有的边．     

r-正则图的边连通度和k-对等性质

既是κ-覆盖又是κ-消去的图称为κ-对等图．给出了边连通度为λ的r-正则图是后．对等图的若干充分条件，得到了如下结论：设r，κ，λ均为正整数，G是边连通度为λ的r-正则图，λ≥2且｜V（G）｜为偶数、若r／λ≤κ≤r-r／λ，则G是κ-对等图．设r为奇数，后为偶数，G边连通度为λ（G）=λ≥2的r-正则图，λ^＊=2[λ／2]＋1．若2≤κ≤r-r／A^＊。则G为κ-对等图．     

有约束条件的r-正则图的k-对等性质

即是k-覆盖又是k-消去的图称为k-对等图．本文研究了有约束条件的r-正则图和k-对等图之间的关系，给出了有约束条件的r-正则图是k-对等图的关于顶点数和边连通度的充分条件．     

一些扫帚图的Ramsey数

给定图G,Ramsey数R(G)是最小的正整数N,满足对完全图K_N的边任意红蓝着色,则或者存在红色子图G或者存在蓝色子图G.扫帚图B_(k,m)是将星图K_(1,k)的中心点与路Pm的一个端点黏成一个点得到的树图.由此得到,当k为大于1的正整数时,R(B_(k,2k-1))=4k-2且R(B_(k,4))=2k+3.     

树的零度与路覆盖数的关系

图的零度是指图G的邻接矩阵A(G)零空间的维度,亦等于其零特征值的重数,用η(G)表示.图的路覆盖是指图G中一组顶点不相交的诱导路的集合,使G的每个顶点都是其中一条路的顶点,G的路覆盖数是指G的最小路覆盖,用ρ(G)表示.2021年Wang给出了图G的零度与路覆盖数的关系：η(G)≤ρ(G),本文刻画了所有满足η(G)=ρ(G)的树.     

轮和路的广义Mycielski图的星全染色

图G的一个正常全染色被称作G的星全染色,如果G中任意路长为2的点和边着色均不相同.图的全部星k-全着色中最小的数k称为它的星全色数.讨论轮和路的广义Mycielski图的星全染色问题,得到不同情况下它们的星全色数,其中每个点的色集合包含该点及其关联边的颜色.