A class of finite groups with complete character degree graphs

In this paper, we construct a new class of finite groups whose common divisor graphs are complete graphs, while there is no prime dividing all the nontrivial degrees.     

完全图中的正常染色的路和圈

令$K_{n}^{c}$表示$n$ 个顶点的边染色完全图.
令 $\Delta^{mon}
(K_{n}^{c})$表示$K^c_{n}$的顶点上关联的同种颜色的边的最大数目.
如果$K_{n}^{c}$中的一个圈（路）上相邻的边染不同颜色,则称它为正常染色的.
B. Bollob\'{a}s和P. Erd\"{o}s (1976) 提出了如下猜想：若 $\Delta^{{mon}}
(K_{n}^{c})<\lfloor \frac{n}{2} \rfloor$, 则$K_{n}^{c}$中含有一个正常染
色的Hamilton圈. 这个猜想至今还未被证明.我们研究了上述条件下的正常染色的路和圈.     

线图上的团染色问题

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

具有唯一K_k- 因子的最大图

这里考虑的是简单图.图 G 的 K_k-因子是 G 的这样一种支撑子图,它的每个连通片皆同构于 k 个节点的完全图 K_k.本文给出:如果 G 具有唯一的 K_k-因子,则|E(G)|≤n~2·k(k-1)/2;进而,对于|E(G)|=n~2·k(k-1)/2的图 G 完全确定了 G 的结构.     

基于Hamilton路模型的蛋白质结构预测的研究

提出一种基于Hamilton路模型的新方法研究蛋白质结构预测问题,为使结构匹配序列,把已知蛋白质的3D结构信息转化为一个加权的完全图Kn,则求这个特定空间结构所匹配的氨基酸残基序列问题转化为求Kn图的最小H路问题.用此方法研究了72个单链蛋白质结构,结果表明Kn图的最小H路对应此蛋白质的序列,图的顶点数n与最小H路总长度成正比.     

有一个实现包含Kr +1的可图序列

设K _{r +1}是一个r +1个顶点的完全图. 一个可图序列π =(d₁, d₂,…, d_n)称为是蕴含K _r+1 -可图的, 如果π有一个实现包含 K _{r +1}作为子图. 该文进一步研究了蕴含K _{r+1 -}可图序列的一些新的条件, 证明了这些条件包含文献[14,10,11]中的一些主要结果和当n≥5r/2 +1时,σ(K _r+1, n)之值(此值在文献[2]中被猜测, 在文献[6,7,8,3]中被证实). 此外, 确定了所有满足n≥5, d₅≥4 且不蕴含K₅ -可图序列π=(d₁, d₂,…, d_n)的集合.     

一类随机图的演化

定义一随机图过程:如果图Gt-1不是完全图时,图Gt分别以概率p和q加一个点和一条有向边;如果图Gt-1是完全图时,则以概率1加一个点．研究图Gt顶点和边的概率分布以及当顶点数固定时,边数的期望界值估计．     

G---的平面性

设G是一个简单图,其全图G 是以V(G)∪E(G)为顶点集的图,其中顶点x和y相邻当且仅当下面的一个条件成立: (i) x,y∈ V(G) ,且x和y在G中相邻, (ii) x,y∈ E(G) ,且x和y在G中相邻, (iii) x和y分别属于V(G)和E(G) ,且它们在G中关联. G---是全图的补图.在这篇文章中,证明了G---是平面的充要条件是 V(G) ≤ 3或者G同构于2K2,C4, K4- e,K4, 2K1 K3, K1,4, K1 K1,3,2K1 P3.     

单圈图的最大特征值序

主要讨论了单圈图按其最大特征值进行排序的问题，确定了该序的前六个图。     

有向全图的幂敛指数和周期

设G是有向图,T(G)表示G的有向全图.本文得到了它们的幂敛指数k(G)和k(T)之间的关系:对任何有向图G,周期p(T(G))=1;当G是本原图时,k(T)≤k(G)+1,文中给出了取得k(G)+1的两类图;当G是无圈图时,k(T)=2k(G)-1,当G是有向圈时,k(T)=2|V(G)|-1,当G是强连通时得到了k(T)的一些估计.