n圈中辐图的团覆盖数和团划分数

本主要讨论Petersen图的一类推广图－n圈中辐图的团覆盖数和团划分数,由此得出该图的团覆盖数和团划分数相等的结论,同时给出了其在不同情况下的计算公式。     

线图上的团染色问题

设G=(V,E)为简单图, G的每个至少有两个顶点的极大完全子图称为G的一个团. 图的团染色定义为给图的点进行染色使得图中没有单一颜色的团, 也就是说每一个团具有至少2种颜色.图的一个k-团染色 是指用k 种颜色给图的点着色使得图G 的每一个团至少有2种颜色.图G的团染色数\chi_{C}(G)是指最小的数k使得图G 存在k-团染色. 首先指出了完全图的线图的团染色数与推广的Ramsey 数之间的一个联系, 其次对于最大度不超过7的线图给出了一个最优团染色的多项式时间算法.     

无爪图上团横贯数的界

设 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-连接图这三类无爪图的团横贯数不超过其阶数的一半.     

正则图的团横贯数的界

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

可实现布尔矩阵的容度与无向图的团覆盖数

讨论了可实现布尔矩阵的容度问题.将可实现布尔矩阵看成是无向图,我们证明了可实现布尔矩阵的容度等于其相应无向图的团覆盖数与孤立点数之和,并给出了通过计算容度来计算团覆盖数,以及通过计算团覆盖数来计算容度的算法框架.     

几类积图的团染色数

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

实现同一度序列的图的最大团数

图G中最大完全子图的阶数称为G的团效．ω(π)和γ(π)分别表示实现度序列π=(d_1,d_2,…,d_n)的图的最大团数和最小团数．Erds,Jacobson和Lehel开始考虑确定具有相同度序列π的图的可能的团数问题．他们证明了对于充分大的n,有ω(π)-γ(π)-n一2n~(2/3)．在本文中,我们首先估计了一类特殊可图序列的ω(π)之值,其次我们建立了一个估计任意可图序列π的ω(π)之值的算法．     

团剖分问题的复杂性

本文考虑分离图和树的平方图上团剖分问题的复杂性.文中的图均为无向简单图,团是指完备子图.分离图是指其点集可剖分为一个团和一个独立集之并的图.图 G 的团剖分是一组边不相重的团,它们包含了 G 的每条边.成员最少的团剖分叫做最小团部分.这个最小成员数叫做团剖分数,记为 CP(G).图的团剖分问题是 NP—完全的.本文的一个结果是证明了分离图上的团剖分问题仍保持,NP—完全性.     

关于图的团符号控制数

引入了图的团符号控制的概念,给出了n阶图G的团符号控制数γks(G)的若干下限,确定了几类特殊图的团符号控制数,并提出了若干未解决的问题和猜想.     

图的符号团边控制数

本文研究了图的符号团边控制数的问题.利用鸽巢原理,获得了图K_n∨P_m和K_n∨C_m的符号团边控制数,推广了已有的结果.     

Clique coloring of binomial random graphs

A clique coloring of a graph is a coloring of the vertices so that no maximal clique is monochromatic (ignoring isolated vertices). The smallest number of colors in such a coloring is the clique chromatic number. In this paper, we study the asymptotic behavior of the clique chromatic number of the random graph ??(n,p) for a wide range of edge‐probabilities p = p(n). We see that the typical clique chromatic number, as a function of the average degree, forms an intriguing step function.     

Finite Rings Whose Graphs Have Clique Number Less than Five

Let R be a commutative ring and Г(R) be its zero-divisor graph.We com-pletely determine the structure of all finite commutative rings whose zero-divisor graphs have clique number one,two,or three.Furthermore,if R≌ Ri × R2 × … Rn (each Ri is local for i =1,2,3,…,n),we also give algebraic characterizations of the ring R when the clique number of r(R) is four.     

Local Clique Covering of Claw‐Free Graphs

A clique covering of a simple graph G is a collection of cliques of G covering all the edges of G such that each vertex is contained in at most k cliques. The smallest k for which G admits a clique covering is called the local clique cover number of G and is denoted by lcc(G). Local clique cover number can be viewed as the local counterpart of the clique cover number that is equal to the minimum total number of cliques covering all edges. In this article, several aspects of the local clique covering problem are studied and its relationships to other well‐known problems are discussed. In particular, it is proved that the local clique cover number of every claw‐free graph is at most , where Δ is the maximum degree of the graph and c is a constant. It is also shown that the bound is tight, up to a constant factor. Moreover, regarding a conjecture by Chen et al. (Clique covering the edges of a locally cobipartite graph, Discrete Math 219(1–3)(2000), 17–26), we prove that the clique cover number of every connected claw‐free graph on n vertices with the minimum degree δ, is at most , where c is a constant.     

List-Coloring Claw-Free Graphs with Small Clique Number

Chudnovsky and Seymour proved that every connected claw-free graph that contains a stable set of size 3 has chromatic number at most twice its clique number. We improve this for small clique size, showing that every claw-free graph with clique number at most 3 is 4-choosable and every claw-free graph with clique number at most 4 is 7-choosable. These bounds are tight.     

若干图类的Wiener指数的极值

一个图的Wiener指数是指这个图中所有点对的距离和.Wiener指数在理论化学中有广泛应用. 本文刻画了给定顶点数及特定参数如色数或团数的图中Wiener指数达最小值的图, 同时也刻画了给定顶点数及团数的图中Wiener指数达最大值的图.     

Clique partitioning with value-monotone submodular cost

We consider the problem of partitioning a graph into cliques of bounded cardinality. The goal is to find a partition that minimizes the sum of clique costs where the cost of a clique is given by a set function on the nodes. We present a general algorithmic solution based on solving the problem variant without the cardinality constraint. We obtain constant factor approximations depending on the solvability of this relaxation for a large class of submodular cost functions which we call value-monotone submodular functions. For special graph classes we give optimal algorithms.     

图的支配划分与最小团的关系

本文用色函数讨论了图Ｇ的团图Ｋ（Ｇ）为奇圈时ｃ（Ｇ）≤ｄ（Ｇ）成立的一个充分条件和Ｋ（Ｇ）为简单连通图时ｃ（Ｇ）≤ｄ（Ｇ）成立的一个充分条件．     

Clique coverings and partitions of line graphs

A clique in a graph G is a complete subgraph of G. A clique covering (partition) of G is a collection C of cliques such that each edge of G occurs in at least (exactly) one clique in C. The clique covering (partition) numbercc(G) (cp(G)) of G is the minimum size of a clique covering (partition) of G. This paper gives alternative proofs, using a unified approach, for the results on the clique covering (partition) numbers of line graphs obtained by McGuinness and Rees [On the number of distinct minimal clique partitions and clique covers of a line graph, Discrete Math. 83 (1990) 49-62]. We also employ the proof techniques to give an alternative proof for the De Brujin-Erd?s Theorem.