弦图上团划分数问题的复杂性

本文得到下述结果:(1)在无K_4图上或在弦图上,求团划分数问题是NP——困难的;(2)找到在无K_4弦图上求团划分数的线性算法和在弦图上求团覆盖数的线性算法。     

三角化图的团划分数

在本文,我们证明了下述结果:(1)如果G=(V,E)是72个顶点的三角化图,则K(G)=α(G)≤cc(G)≤cp(G),cc(G)≤n-1,其中图G顶点独立数为α(G),它可在O(|V|+|E|)时间内求出;(2)如果G=(V,E)是n个顶点的特殊三角化图,V=S∪K,具有度序列为n-1≥d_1≥d_2≥…≥d_n,若对于S中任意顶点对x_i,x_j有|Adj(x_i)∩Adj(x_i)|≤1,则α(G)≤cp(G)≤α(G)+δ,其中,m=w(G)是图G的最大团的顶点个数。     

关于弦图的团序列

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

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

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

关于图的控制集划分

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

区间图上的并行算法设计

对区间图上的图问题并行求解,给出两种算法设计方法,利用这两种方法,对最小团覆盖,最大团,最大独立集,最小支配集,Hamiltonian回路,最佳道路覆盖,最小带宽和Steiner树的计算问题,在EREW PRAM模型上给出O(logn)时间,使用O（n)处理器的高效并行算法。     

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

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

图支配数的若干问题

本文研究了图的支配数和图的独立数、覆盖数间的关系，得到了一系列不可改进的结果。     

两类广义图r-冠图的分数色数

图的着色问题是图论的重要研究课题之一,分数色数作为正常色数的一个推广在计算机的许多领域中有着重要的应用.此处给出了广义圈、广义轮图的r-冠图的分数色数的计算公式.     

广义θ-图的分数关联色数

本文从分数色数的定义和已有结论出发,针对两种不同的情况分别给出广义θ-图的分数关联色数,并由此进一步给出广义θ-图的r-冠图的分数关联色数,得到如下结论:incf(θk)={k+1 ,至少有一条路径的长不为2/k2/d-1所有路径的长均为2;incf(Ir(θk))=inc(Ir(θk))=k+r+1.     

一致膨胀图和广义圈、广义轮图的分数色数

图的着色问题是图论的重要研究课题之一,分数色数作为正常色数的一个推广在计算机的许多领域中有着重要的应用.文章研究了一致膨胀图分数色数与原图分数色数之间的关系,并给出广义圈、广义轮图的分数色数.     

不含某些图作为导出子图的图的色数

Erods证明了对于任意一个图G,χ(G)-ω(G)可以任意大。因此,对一般图而言,其色数不一定能找到一个与团数有关的上界。文章主要讨论一类特殊的F-free图的色数和团数的关系。设图G=(V,E)是一个不含K1,k+1+e、C4和C4+e为导出子图的连通图,不是星图和奇圈。若α(G)≥k≥3,则χ(G)≤(k(k-1)/2)ω(G)。     

图的路覆盖数的上界

设G是简单图。记ρ(G)为覆盖图G所需路数的最小值。本文证明了ρ(G)≤[2n/3];且若G是连通图,则ρ(G)≤[3n/5]。     

球面经纬线图的分数色数

图的着色问题是图论的重要研究课题之一，分数色数作为正常色数的一个推广在计算机的许多领域中有着重要的应用．本文给出了球面经纬线图以及它的r-冠图的分数色数，分数关联色数和分数全色数．     

关于图的领域复盖

图G＝（V，E）中一个点V的领域是点V及其邻点导出的G的子图。领域复盖问题就是求一级量小个的领域，使其复盖子G的每一条边。本文证明了无三角形图上和分离图上的领域复盖问题是NP－完全问题。通过研究集族的强Helly性质，得到了领域复盖问题可转化为团复盖问题的条件一图的领域二分具有强Helly性质。文中给出了弦图的领域二分图具有强Helly性质的禁用子图形式的充分必要条件。