无爪图上团横贯数的界

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

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

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

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

设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-团之中,得到了它的横贯数的上界和独立数的可达下界.

正则图的最大-团横贯数与减最大-团横贯数

本文首先得到了阶数为n、团数为k的连通k-正则图的最大-团横贯数的上界n/k以及n阶连通无爪3-正则图的最大-团横贯数的下界n/4,并对达到这些界的极值图进行了刻画。然后对阶数为n、团数为ω(G)的任意图G的减最大-团横贯数给出了一个紧的下界1+ω(G)-n,同时对阶数为n、团数为k的连通k-正则图的减最大-团横贯数呈现了一个上界n/k,并刻画了达到这个上界的极值图。

正则图的团横贯数的界

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

无三角形3-正则图的几个参数的界

图G的一条边称为割边是指删去该边后,使得余下的图的连通分支数增加。图G中的一个两两不相邻的边子集称为图G的一个匹配。图G的一个最大匹配的边数称为图G的匹配数。图G中的一个与G的每个团都有交的顶点子集称为G的一个团横贯集,图G中元素个数最少的团横贯集的顶点数称为G的团横贯数。本文针对n阶连通无三角形的3-正则图G=(V(G),E(G)),首先给出了其割边数的一个上界(n-10)/4;其次对它的匹配数得到了一个下界(11n-2)/24;再次对它的线图的团横贯数呈现了一个上界(13 E(G)+3)/36。同时刻画了达到这些界的极值图。