平面图上的团横贯数与独立数

设G为简单图,若G的点子集S与图中的每个团都有非空的交,则称S是图G的一个团横贯集,这里G的团是指图中的极大完全子图且至少包含两个点.图G的最小团横贯集所含点的数目称为G的团横贯数,记作τC(G).如果G的每条边至少包含在一个t阶完全子图中且τC(G)≤|V(G)|/t,则称G具有〈t〉一性质.提出了平面图分离4-团的概念.首先证明了最大度不超过5的平面图具有〈t〉-性质.其次,对任意平面图G,若它不含分离4-团且每条边都包含在一个4-团之中,得到了它的横贯数的上界和独立数的可达下界.     

正则图的团横贯数的界

设D是图G的一个顶点子集, 若D含有G的每个团中至少一个顶点, 则D称为G的团横贯集. 图G的团横贯数是指它的最小团横贯集中顶点的数目, 记作τ_c(G). 本文研究正则图的团横贯数. 首先建立了正则图的团横贯数的上、下界, 且刻画了达到下界的极值图. 其次, 对无爪三次图, 得到了改进的可达上、下界并刻画了达到下界的极值图.     

最小填充问题的可分解性

起源于稀疏矩阵计算和其它应用领域的图G的最小填充问题是在图G中寻求一个内含边数最小的边集F使得G F是弦图.这里最小值|F|称为图G的填充数,表示为f(G).作为NP-困难问题,该问题的降维性质已被研究,其中包括它的可分解性.基本的可分解定理是:如果图G的一个点割集S是一个团,则G经由S是可分解的.作为推广,如果S是一个"近似"团(即只有极少数边丢失的团),则G经由S是可分解的.本文首先给出基本分解定理的另外一个推广:如果S是G的一个极小点割集且G-S含有至少|S|个分支,则G经由S是可分解的;其次,给出了这个新推广定理的一些应用.     

序列平行图的最小填充

起源于稀疏矩阵计算和其它应用领域的一个图G的最小填充问题就是在G中寻找一个边数| F |最小的添加边集F,使得G+F是弦图.这里最小值| F |称为图G的填充数,表示为f(G).对一般图来说,这个问题是NP-困难问题.一些特殊图类的最小填充问题已被研究.本文给出了序列平行图G的最小填充数的具体值.     

弦图的补图的最小填充

从图论观点讲,最小填充问题就是在一个图G中添加边集F,使得图G的母图G F是一个弦图而且所添边的边数| F|是最小的,其中最小值| F|称为图G的填充数,表示为f( G) .对一般图来说,最小填充问题是NP-困难的,但是对一些特殊图类来说,这个问题是在多项式时间内可解的.本文给出了弦图的补图-G的填充数f(-G) .     

一个关于近-三角剖分嵌入的内插定理

一个近三角剖分嵌入是指一个图嵌入在一个曲面上,使得至多可能有一个面不是三角面。在本文中我们证明了如下结果：如果一个图G在某个可定向曲面S_h上有三角剖分嵌入,那么G在S_k上有一个近三角剖分嵌入,这里k=h,h 1,…,[β(G)/2],而β(G)是图G的Betti数。     

无向路图和块图上的混合控制

图G=(V,E)的一个混合控制集是一个满足如下条件的集合DV∪E:不在D中的每个点或每条边都相邻或关联于D中的至少一个点或一条边.确定图的最小基数的混合控制集的问题称为混合控制问题.本文研究混合控制问题的算法复杂性,证明了混合控制问题在无向路图上是NP-完全的,但在块图上有线性时间算法.无向路图和块图都是弦图的子类,又是树的母类.     

关于两类平面图及相关图的L(d1,d2)-标号问题

图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.本文将L(2,1)-标号推广到L(d1,d2)-标号,并得出了平面三角剖分图、立体四面体剖分图、平面近四边形剖分图的L(d1,d2)-标号的上界,作为推论,本文证明了对上述几类图,有上述猜想成立.     

关于图的L(d,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.此文研究了作为L(2,1)-标号问题的推广的L(d,1)-标号问题,并得出了平面三角剖分图、立体四面体剖分图、平面近四边形剖分图的L(d,1)-标号的上界,作为推论证明了对上述几类图该猜想成立.     

具有两个同阶轨道的双轨道图的圈边连通度

一个边割被称为圈边割,如果该边割能分离图的两个不同圈.如果一个图有圈边割,称该图为圈边可分离的.一个圈边可分离图G的最小圈边割的阶数被称为圈边连通度,记作cλ（G）.定义：ζ（G）=min{w（X）｜X导出G的最短圈},其中w（X）为端点分别在X和V（G）-X中的边的数目.如果一个圈边可分离图G使得cλ（G）=ζ（G）成立,称该图是圈边最优的.Tian和Meng在文章[11]以及Yang et al在文章[15]中研究了两种不同的双轨道图的圈边最优性.本文我们将研究具有两个同阶轨道的双轨道图的圈边连通度.     

3连通图的可去边数

设 e是 3连通图 G的一条边 ,如果 G- e是某个 3连通图的剖分 ,则称 e是 G的可去边 .本文给出了 3连通图的可去边数依赖于极大半轮的下界以及达到下界的极图 .     

没有K4-图子式的图的无圈边色数

一个图G 的无圈k- 边染色是指G 的一个正常的不产生双色圈的k- 边染色. G 的无圈边色数a′(G) 定义为使得G 有一个无圈k- 边染色的最小的整数k. 本文完全刻画了最大度不为4 的没有K₄-图子式的图的无圈边色数.     

树的彩虹控制数的一个多项式时间算法

设G是—个边染色图,G的彩虹子图是所有边都染不同颜色的子图.覆盖V(G)的不相交彩虹星的集合称为彩虹控制星集,图G最小彩虹控制星集的大小称为彩虹控制数,记为γ(G).本文给出了—个在边染色树T上寻找最小彩虹控制星集从而得到T的彩虹控制数的多项式时间算法.     

无爪图上团横贯数的界

设 G=(V,E) 为简单图,图 G 的每个至少有两个顶点的极大完全子图称为 G 的一个团. 一个顶点子集 S\subseteq V 称为图 G 的团横贯集, 如果 S 与 G 的所有团都相交,即对于 G 的任意的团 C 有 S\cap{V(C)}\neq\emptyset. 图 G 的团横贯数是图 G 的最小团横贯集所含顶点的数目,记为~${\large\tau}_{C}(G)$. 证明了棱柱图的补图(除5-圈外)、非奇圈的圆弧区间图和 Hex-连接图这三类无爪图的团横贯数不超过其阶数的一半.     

图的边覆盖染色中的分类问题(英文)

设 G是一个图 ,其边集是 E( G) ,E( G)的一个子集 S称为 G的一个边覆盖 ,若 G的每一点都是 S中一条边的端点 .G的一个 (正常 )边覆盖染色是对 G的边进行染色 ,使得每一色组都是 G的一个边覆盖 ,使 G有 (正常 )边覆盖染色所需最多颜色数 ,称为 G的边覆盖色数 ,用χ′c( G)表示 .已知的结果是对于任意简单图 G,都有 δ- 1≤ χ′c( G)≤ δ,δ是 G的最小度 .若 χ′c( G) =δ,则称 G是 CI类的 ;否则称为 CII类的 .本文主要研究了平面图及平衡的完全 r分图的分类问题     

关于偏序集相关联图的色数

对于每一个含有最小元素0的偏序集（P,≤）可以得到一个与其关联的图G（P）.本文主要通过代数的方法研究了所得关联图G（P）的性质,证明了如果G（P）的色数和团数是有限的,那么色数和团数都仅比P的极小素理想的个数大1.     

几类积图的团染色数

设G=（VE）为简单图,V和E分别表示图的点集和边集．图G的一个k-团染色是指点集V到色集{1,2,…,k）的一个映射,使得G的每个至少含两个点的极大团都至少有两种颜色．分别给出了任意两个图的团色数与它们通过笛卡尔积、Kronecker积、强直积或字典积运算后得到的积图的团色数之间的关系．     

一个关于球面和环面上嵌入图的近-三角剖分嵌入的内插定理(I)

一个近-三角剖分嵌入是指一个曲面上的嵌入图使得几乎所有的面都是三角形,至多只有一个可能的例外.文中作者证明了如下结论:如果一个图G 在球面S₀(或环面S₁)上有近-三角剖分嵌入,那么G在每一个可定向曲面S_k有近-三角剖分嵌入,其中k=h,h+1,\cdots ,\lfloor\frac{\beta(G)}{2}\rfloor$, 而h=0(或1)并且β(G)是图G的Betti数.特别地,G是上可嵌入的.     

正则图的限制性边连通度

将连通图分离成阶至少为二的分支之并的边割称为限制性边割,最小限制性边割的阶称为限制性边连通度. 用λ′(G)表示限制性连通度,则λ′(G)≤ξ(G),其中ξ(G)表示最小边度. 如果上式等号成立,则称G是极大限制性边连通的. 本文证明了当k＞|G|/2时,k正则图G是极大限制性边连通的,其中k≥2, |G|≥4; k的下界在某种程度上是不可改进的.     

最大度与最小度相差不超过2的图的平衡judicious划分

图G的顶点集V(G)的一个二部划分V_1和V_2叫做平衡二部划分,如果||V_1|-|V_2||≤1成立.Bollobas和Scott猜想:每一个有m条边且最小度不小于2的图,都存在一个平衡二部划分V_1,V_2,使得max{e(V_1),e(V_2)}≤m/3,此处e(V_i)表示两顶点都在V_i(i=1,2)中的边的条数.他们证明了这个猜想对正则图(即△(G)=δ(G))成立.颜娟和许宝刚证明了每个(k,k-1)-双正则图(即△(G)-δ(G)≤1)存在一个平衡二部划分V_1,V_2,使得每一顶点集的导出子图包含大约m/4条边.这里把该结论推广到最大度和最小度相差不超过2的图G.