边色数分类的两个充要条件及其性质

设图 G 是简单连通图,由 Vizing 定理知:Δ(G)≤x′(G)≤Δ(G)+1.其中Δ(G)表示图 G 的最大顶点次,x′(G)是图 G 的边色数.若 x′(G)=Δ(G),则称 G 为第一类图,并简记为 G∈C~1;若 x′(G)=Δ(G)+1,则称 G 为第二类图,并简记为 G∈C~2.其他图论述语见一般教科书。如果 G 满足|E(G)|>Δ(G)[(|V(G)/2|)],则称 G 为满图。显然,若图 G 为满图,则     

Kronecker乘积图的平面性

设G1和G2是两个连通图,则G1和G2的Kronecker积G1×C2定义如下:V(G1×G2)=V(G1)×V(G2),E(G1×G2)={(u1,v1)(u2,v2):u1u2∈E(G1),v1v2∈E(G2)}.该文证明了如果G=G1×G2是平面图并且︱Gi︱≥3,那么G1和G2都是平面图;还完全确定了Pn×G2的平面性,n=3,4.     

关于图的和宽问题

设 f 表示图 G 顶点上的标号函数,定义 b(G)=min max{f(u)+f(v)|边(u,v)∈E(G)}.其中图 G 是简单、连通图。称 b(G)为 G 的和宽.期望利用 b(G)来研究带宽 B(G)。证得2B(G)≤b(G)-1及 b(G)≥p(G)+δ(G),b(G)≥△(G)+2,b(G)+b(G~C)≥2p(G)+2,p(G)=|V(G)|。     

关于图的拟拉普拉斯矩阵的永久式

设G是一简单无向图，A(G)为G的邻接矩阵，D(G)为G的顶点度对角矩阵，Q(G)=D(G)—A(G)称为G的拟拉普拉斯矩阵，本文研究Q(G)的永久式，得到perQ(G)的两个表示公式及perQ(G)的一些下界。     

合成图的全着色

对于任意简单图G,Δ(G)和t(G)分别表示G的最大度和全色数.本文证明了如果G的全色数满足t(G)≤Δ(G)+2,则合成图G[(?)_m]和K_n[G]的全色数满足t(G[(?)_m])≤Δ(G[(?)_m])+2,t(K_n[G])≤Δ(K_n[G])+2。     

对称群S_n(n≤14)的新刻画

设G是有限群,o_1(G)表示G中最高阶元素的阶,n_1(G)表示G中最高阶元素的个数.设G一共有r个o_1(G)阶元,且中心化子的阶两两不同,并依次设这些中心化子的阶为c_1(G),c_2(G),…,c_r(G).令ONC_1(G)={o_1(G);n_1(G);c_1(G),c_2(G),…,c_r(G)},称为G的第一ONC-度量.本文得到:设G为有限群且G的素图不连通,则G?S_n(n≤14)当且仅当ONC_1(G)=ONC_1(S_n).     

图的直积和字典积的Laplacian谱和Kirchhoff指数

由图G1、G2的Laplacian谱得到了它们的直积G1×G2和字典积G1[G2]的Laplacian谱,并计算了R(G1×G2)和R(G1[G2]).     

高度图的全色数

证明了：如果图G的最大度顶点数r(G）满足r(G)≥|V（G）|-△（G）-1,且δ（G） 2△（G）≥5/2|V（G）| 3/2,则G的全色数xT(G)=△（G） 1。     

平面图的平方染色数的一个新上界

令V(G)、E(G)、Δ(G)和χ(G)分别为G的顶点集、边集、最大度和色数。图G的平方图,记为G2,指的是一个图满足条件:V(G2)=V(G),并且uv∈E(G2)当且仅当1≤dG(u,v)≤2。证明了若G是Δ(G)≤6且围长g(G)≥5的平面图,则χ(G2)≤Δ(G)+8。     

线图中2-因子分支数的一些结果

设图G为一简单图,顶点集为V(G),边集为E(G),G的线图为L(G),如果一个图G满足κ(G)≥α(G)或dia(G)≤2,则它的线图L(G)为哈密顿的,在相同条件下,本文考虑L(G)中2-因子的分支数.     

边色数分类的几个结果

设图G为简单连通图,由Vizing定理知:△(G)≤x′(?)G)≤△(G) 1,其中,△(G)表示图G的最大顶点次,x′(G)是图G的边色数。若x′(G)=△(G),则称G为第一类图,并简记为G∈C′;若x′(G)=△(G) 1,则称G为第二类图,并简单记为G∈C~2。A.J.W,Hilton在[1]中提出了如下猜想:如果G是简单图,且(ⅰ)△(G)>2/3(|V(G)|-3),(ⅱ)δ(G)≤1,则G∈C′。本文的目的是围绕着这一猜想,得出了几个有关结果。     

关于团图的一个注记

在这个注记中,我们将[1]定理3·1改进成:图G满足条件2~(|G|-ω(G))=|K(G)|当且仅当G是Turan图T(|G|,ω(G))的子图且同时G包含一个子图同构于[1]定理2·3的证明中引入的Hedman图H(|G|,ω(G))。我们还指出[1]定理3·2是错误的。事实上我们进一步证明了:如果图G满足条件2~(|G|-ω(G))=|K(G)|,则或者K(G)是Neumann图或者K(G)是完全图,并且K(G)为完全图当且仅当Δ(G)=|G|-1。     

关于Janko群的新刻画

设G为有限群,o_1(G)表示G中最高阶元素的阶,n_1(G)表示G中最高阶元素的个数.设G一共有r个o_1(G)阶元,其中心化子的阶两两不同,并依次设这些中心化子的阶为c_i(G)(i=1,2,…,r).令ONC_1(G)={o_1(G);n_1(G);c_1(G),c_2(G),…,c_r(G)},称ONC_1(G)为G的第一ONC-度量,用第一ONC-度量ONC_1(G)刻画了Janko群.     

具有特殊循环子群个数的有限群

设G为有限群,C(G)为G的循环子群的集合.|C(G)|对G的结构有一定的影响.例如,G为初等交换2-群当且仅当|C(G)|=|G|.一些作者已经分类了满足|G|-|C(G)|≤3的群.利用循环子群个数与|G|的等式关系,分类了所有满足|G|-|C(G)|=4的有限群.     

点邻域完整度等于1,2的树

设G是图,G的点颠覆策略S是G的一个点子集,它的闭邻域从G中删去,幸存子图记为G/S.G的点邻域完整度VNI(G)定义为:VNI(G)=mins V(G){|S| ω(G/S)},S是G的任意的点颠覆策略,ω(G/S)是G/S的最大连通分支的阶.刻画了点邻域完整度为1,2的树.     

关于哈密尔顿指数的综述

图G的线图L（ G）是指以G的边集E（ G）为顶点集且L（ G）的2个顶点邻接当且仅当它们在G中有公共顶点。 n次迭代线图Ln（G）递归地定义为L0（G）=G,Ln（G）=L（Ln-1（G））（n∈N=｛0,1,2,…｝）,其中L1（ G）=L（ G）并且假设Ln-1（ G）非空,使得Ln（ G）是哈密尔顿的最小整数n称为哈密尔顿指数,用h（ G）表示。该文综述了（类）哈密尔顿指数的一些结果。     

P_5群的Chermak-Delgado格

简称Chermak-Delgado格为CD格,CD(G)代表群G的CD格.若|G|=pn,|G∶Z(G)|=pi,G∈CD(G),则称G是Pi群.研究了|G∶Z(G)|=p_5群G的CD格,转化为研究P5群的CD格.确定了P5群的CD格的Hasse图.     

中心自同构几乎是内自同构的有限p-群

有限p-群G的中心核K(G)是G的每一中心自同构都不变的全体元素所构成的子群.如果G是幂零类为2的p-群,首先给出了|Aut_c(G):Inn(G)|与|Z(G):K(G)|相等的充分必要条件,其次研究了|Aut_c(G):Inn(G)|与|Z(G):K(G)|相差一个p的倍数的条件.     

图的特征根

设G=(V(G),E(G)) 是顶点集为V(G)边集为E(G)的简单图. 用A(G)表示图G的邻接矩阵.A(G)的特征根称为图 G的特征根.主要研究图Ksn-s的邻接谱.     

树的最大与次小Laplacian特征值和的上界

随着计算机技术和网络技术的不断发展,图的谱被广泛应用于网络拓扑结构的特征分析,Laplacian矩阵的谱(特别是最大特征值和次小特征值)在网络结构中扮演重要角色.设G=(V,E)是一个具有n个顶点的简单图,A(G)为G的邻接矩阵,D(G)为G的度对角矩阵.定义G的Laplacian矩阵为L(G)=D(G)-A(G),设L(G)的特征值为μ1(G)≥μ2(G)≥…≥μn-1(G)≥μn(G)=0,最大特征值μ1(G)称为图G的Laplacian谱半径;次小特征值μn-1也称作图G的代数连通度.本文讨论了树的L(G)的最大与次小特征值和μ1(G)+μn-1(G)的上界,得到几个有意义的结论.