图乘积的分数色数

在文中我们对两个图的强乘积的分数色数进行了研究.任意给定两个图G和H,我们证明了ω(G)ω(H)≤χf(GH)≤χ(G)χ(H),这里ω(G)表示图G的最大团所含顶点的个数,χf(G)和χ(G)分别表示图G的分数色数和色数.从而我们可以通过图G和H本身的性质来对它们的强乘积的分数色数和色数进行估计.     

关于图能量上界的注释

对一个简单连通图G V(,E)来说,其能量表示为图G V(,E)的邻接矩阵特征值的绝对值之和.在文献[1]中,Kinkar Ch.Das和Seyed A.Mojallal用定点个数、边数、团数以及顶点的最小度数给出了一个图能量的新上界.在计算验证中我们发现一点瑕疵,本文给予修正,并正确给出修正的图能量的上界.     

关于弦图的团序列

设G=(V,E)是一个有限无向简单图,C_k是G中具有k个点的完备子图的数目。序列(C_1,C_2,…)称为图G的团序列。本文给出了整数序列是弦图的团序列的充分必要条件、两个弦图有相同的团序列的充分必要条件和弦图k连通的充分必要条件。     

关于一类图的Hamilton性

设G=(V,E)为n阶简单图,如果存在V的一个分划(V_0,V_1,…,V_m)使得: (ⅰ)或者V_0为G的团,或对每一v∈V_0,d(υ)≥n/2, (ⅱ)对于i=1,…,m,V_i是G的团,并且N(V_i)V_0UV_i, 则称G为范型图。本文给出关于这类图的Hamilton性的两个结果。     

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

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

不含K1＋P3和C4作为导出子图的图的色数

Erodos证明了对于一个图G ,χ（G）-ω（G）可以任意大。因此,对一般图而言,其色数不一定能找到一个与团数有关的上界。文章主要研究了一类 F-free图的色数和团数的关系。得到了如果图G是一个不含K 1＋ P3和C4作为导出子图的图,那么当α（G ）≥3时,χ（G ）＝ω（G ）;当α（G ）＝2时,χ（G ）n ≤2ω（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。同时刻画了达到这些界的极值图。
     

随机图G（n，P）中k-团的相变性质

随机图G（n,P）模型是随机图理论中最重要的模型之一。该模型中有两个参数n和P,n表示图中的顶点数,P表示图中的任意两个不同顶点之间独立生成边的概率。证明了随机图G（n,P）中存在k一团的临界值为P=n^-2/k-1;同时证明了随机图G（n,P）中具有k≥3顶点孤立团的连通分量数服从均值λ=e^-x-k3/k!的泊松分布;最后,数值实验分析随机图G（n,P）实例中3-团托：和10一团的相变。数值实验结果表明,实验与理论结果相符。     

关于图的符号团控制数

对于一个非空图G=(V,E)和一个函数f:E→{-1,+1},若SE,则记f(S)=∑_e∈Sf(e).若对于G中每个非平凡的团K均满足f(E(K))≥1,则f被称为G的一个符号团控制函数,G的符号团控制数表达为     

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

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

图的符号控制划分数的Nordhaus-Gaddum型结果

设G=(V,E)是一个简单图,在图G的所有符号(全)控制族中,基数最大的符号(全)控制族包含的符号(全)控制函数的数目称为是图G的符号(全)控制划分数.首先给出图的符号控制划分数的Nordhaus-Gaddum型结果,接下来,又给出了图的符号全控制划分数的Nordhaus-Gaddum型结果.     

两类图的边控制集划分

通过分类归纳的方法,对图的边控制集划分问题进行了探讨,研究了两类特殊图的边控制集划分问题,获得了一些相关结论:得到了扇形图F_n的集边控制数和全集边控制数,并确定了乘积图P_2×P_n的全集边控制数.     

关于图的控制集划分

通过分类归纳的方法,对图的控制集划分问题进行了研究,给出了控制划分数d(G)和全控制划分数d1(G)的上界,并确定了d(Pm×Pn)的所有确切值和d(Cm×Pn)部分的确切值.     

图的负全控制划分数

定义了图的负全控制划分数，得到了负全控制划分数的存在性和其与边数、最小度的关系，并给出其在部分完全图上的准确值和在一般图上的一个上界。