遗传图类的色临界图

1

作者 黄申为 夏雯 《数学进展》 CSCD 北大核心 2023年第6期961-979,共19页

本文对一些特殊图类的色临界图的研究结果做了一个总结.若某个图的色数是k,但它的任何真子图的色数都小于k,则称该图是k-临界的.对于某个图族H,如果某个图不包含任何H中的图作为导出子图,则称该图为H-free的.如果某个图类对某个图族H是H... 本文对一些特殊图类的色临界图的研究结果做了一个总结.若某个图的色数是k,但它的任何真子图的色数都小于k,则称该图是k-临界的.对于某个图族H,如果某个图不包含任何H中的图作为导出子图,则称该图为H-free的.如果某个图类对某个图族H是H-free的,则称该图类为遗传图类,且H中的图被称为该图类的禁用导出子图.本文主要研究禁用一个或两个导出子图的遗传图类的色临界图的刻画问题和有限性问题,其中刻画问题寻求给定图类中色临界图的完全刻画,而有限性问题探究给定图类中k-临界图的数量是否有限.本文对以上两个问题的研究结果进行总结.重点关注这些结果如何随时间的推移而发展,以及用于证明这些结果而采用的关键技术.此外,本文还列出一些重要的公开问题,并给出一些猜想. 展开更多

关键词 图染色 k-临界图 禁用导出子图 计算机搜索 Ramsey定理

原文传递

(2n+1)-可收缩图和2n-对可收缩图

2

作者 林泓 郭晓峰 《数学学报（中文版）》 SCIE CSCD 北大核心 2009年第2期343-352,共10页

令G是一个简单连通图.设S■V(G)且|S|=2n+1,将S收缩为一个顶点后所得到的图记α_((2n+1))(G,S).若G有完美匹配,且对于V(G)的任意一个有2n+1个顶点的子集S,图α_((2n+1))(G,S)有完美匹配,则称G是一个(2n+1)-可收缩图.设S_1,S_2,…,S_(2n)... 令G是一个简单连通图.设S■V(G)且|S|=2n+1,将S收缩为一个顶点后所得到的图记α_((2n+1))(G,S).若G有完美匹配,且对于V(G)的任意一个有2n+1个顶点的子集S,图α_((2n+1))(G,S)有完美匹配,则称G是一个(2n+1)-可收缩图.设S_1,S_2,…,S_(2n)是V(G)的两两不相交的子集且|S_1|=|S_2|=…=|S_(2n)|=2,将S_i (i=1,2,…,2n)分别收缩为一点所得到的图记β_(2n)(G,S_1,S_2,…,S_(2n)).若G有完美匹配,且对于V(G)的任意2n个两两不相交的子集S_1,S_2,…,S_(2n),这里|S_1|=|S_2|=…=|S_(2n)|=2,图β_(2n)(G,S_1,S_2,…,S_(2n))有完美匹配,则称G是一个2n-对可收缩图.本文得到了(2n+1)-可收缩图和2n-对可收缩图的充要条件,并讨论了2n-临界图,(2n+1)-可收缩图,2n-对可收缩图及n-可扩图间的关系. 展开更多

关键词 (2n+1)-可收缩图 2n-对可收缩图 N-可扩图 k-临界图

原文传递

图的4K2—分解

3

作者 董进全 《内蒙古大学学报（自然科学版）》 CAS CSCD 1989年第2期157-161,共5页

关键词 图 4k2-分解 k-临界图 S分解

下载PDF 职称材料

完美整数k-匹配和k-因子临界图

4

作者 张燕红 张磊 任海珍 《数学杂志》 2024年第3期189-194,共6页

本文研究完美整数k-匹配和k-因子临界图的存在性.扩张常数表示图的连通强度,对于正则图,利用扩张常数给出了完美整数k-匹配存在的一个充分条件,这推广了Hamers等人和Cioabǎ等人的结果.此外,对于正则图,基于扩张常数还给出了k-因子临界... 本文研究完美整数k-匹配和k-因子临界图的存在性.扩张常数表示图的连通强度,对于正则图,利用扩张常数给出了完美整数k-匹配存在的一个充分条件,这推广了Hamers等人和Cioabǎ等人的结果.此外,对于正则图,基于扩张常数还给出了k-因子临界图存在的一个充分条件. 展开更多

关键词 完美整数k-匹配 k-因子临界图 连通性 扩张常数

下载PDF 职称材料

最大外可平面图的树图 被引量：1

5

作者 李向东 《河北理工学院学报》 2000年第3期86-88,共3页

通过对最大外可平面图和 K临界图的研究给出三个主要结论( 1 )最大外可平面图的生成树有 2 p- 3* 3棵。( 2 )最大外可平面图的树图GT,Δ( GT)≥ p+ 1。( 3)临界图 G,当 K( G) =1时 ,树图 GT 是平凡图 ,当K( G) =2时 ;树图 GT是

关键词 树图 最大外可平面图 k临界图 生成树

下载PDF 职称材料

关于(ξ,k)-临界图 被引量：1

6

作者 黄元秋 刘彦佩 《应用数学》 CSCD 北大核心 2001年第1期84-89,共6页

设 G为连通图 ,且ξ(G) =k≥ 1 ,若对 G中任意边 e,均有ξ(G\e) =k - 1 ,则称 G为 (ξ,k) -临界图 .本文刻划了ξ- 1 -临界图的若干性质 ,给出了一个图为ξ- 1 -临界图的一些充分或必要条件 ,以及一些ξ- 1 -临界图类 .

关键词 最大亏格 BETTI亏数 上可嵌入 (ξ k)-临界图 连通图

下载PDF 职称材料

(g,f,k)-临界图的一个充分条件

7

作者 周思中 吴建成 《江苏科技大学学报（自然科学版）》 CAS 北大核心 2009年第2期173-175,共3页

设G是一个图,F是G的一个完全因子且ω(F)≥2,g和f是定义在V(G)上的两个整数值函数,且对所有的x∈V(G)有0≤g(x)<f(x).本文证明:若对F的每个分支C,G-V(C)是(g,f,k)-临界图,则G本身也是(g,f,k)-临界图.

关键词 图 完全因子 (G F)-因子 (g f k)-临界图

下载PDF 职称材料

(a,b,k)-临界图的一个充分条件

8

作者 常仁英 《山东大学学报（理学版）》 CAS CSCD 北大核心 2010年第4期21-23,共3页

给出了一个图是(a,b,k)-临界图的孤立韧度条件,并证明该结论在一定意义下是最好的。

关键词 图 孤立韧度 [A B]-因子 (a b k)-临界图

原文传递

(g,f,k)临界图的一个充分必要条件

9

作者 胡杏 《邵阳学院学报（自然科学版）》 2008年第1期12-14,共3页

设G是一个简单图,g和f是两个定义在V(G)上的整数值函数,且对所有的x∈V(G)都满足g(x)≤f(x).如果删除G的任何k个顶点后,图G的其余部分含有一个(g,f)因子,那么称图G为一个(g,f,k)-临界图.本文给出了一个图是(g,f,k)-临界图的一个充要条件... 设G是一个简单图,g和f是两个定义在V(G)上的整数值函数,且对所有的x∈V(G)都满足g(x)≤f(x).如果删除G的任何k个顶点后,图G的其余部分含有一个(g,f)因子,那么称图G为一个(g,f,k)-临界图.本文给出了一个图是(g,f,k)-临界图的一个充要条件,并对这些条件的应用作了讨论。进一步,本文研究了(g,f,k)-临界图的性质。 展开更多

关键词 (G F)-因子 (g f k)-临界图 充分必要条件

下载PDF 职称材料

分数k-因子临界图的条件(英文) 被引量：1

10

作者 李巧 刘岩 《运筹学学报》 CSCD 北大核心 2013年第4期123-130,共8页

设G是一个连通简单无向图,如果删去G的任意k个顶点后的图有分数完美匹配,则称G是分数k-因子临界图.给出了G是分数k-因子临界图的韧度充分条件与度和充分条件,这些条件中的界是可达的,并给出G是分数k-因子临界图的一个关于分数匹配数的... 设G是一个连通简单无向图,如果删去G的任意k个顶点后的图有分数完美匹配,则称G是分数k-因子临界图.给出了G是分数k-因子临界图的韧度充分条件与度和充分条件,这些条件中的界是可达的,并给出G是分数k-因子临界图的一个关于分数匹配数的充分必要条件. 展开更多

关键词 分数完美匹配 分数k-因子临界图 韧度 分数匹配数

下载PDF 职称材料

(a,b,C_k)临界图的判定

11

作者 徐兰 苏贵福 《数学的实践与认识》 CSCD 北大核心 2013年第19期265-268,共4页

设G是一个图且a,b是非负整数,a≤b.如果消去G中的任意一个k-圈,剩下的图有[a,b]-因子,则称图G是(a,b,C_k)-临界图.给出了图是(a,b,C_k)-临界图的充分条件.

关键词 图 孤立韧度 [A B]-因子 （a b C_k）-临界图

原文传递