完全二部图定长的路分解

给出了完全二部图K_n1,n2可以进行{P₄,P₅}-分解的情况.     

完全二部图Kn+1,2n与完全三部图K1,n,2n的厚度关系

图的厚度是指将该图分解为平面生成子图的最小数,它是衡量一个图可平面性的关键指标之一.研究一个图的厚度至关重要,它在超大规模集成电路和网络设计中有着重要应用.目前已经得到一部分图类的厚度的精确值,但完全二部图与完全三部图的厚度关系未完全得到,通过构造完全三部图K_(1,3p+1,6p+2)的一个平面分解得到了完全三部图K_(1,n,2n)的厚度,进而推出完全二部图K_(n+1,2n)与完全三部图K_(1,n,2n)的厚度相等.     

完全四部图■的点被多重集可区别的一般全染色(n1≤n2=n34或n1=n2=n3=n4)

利用反证法、构造染色法和色集合事先分配法,讨论完全四部图K_n1,n2,n3,n4(n₁≤n₂=n₃4或n₁=n₂=n₃=n₄)的顶点被多重集可区别的一般全染色,给出一个最优染色方案,并确定相应染色的色数.     

完全偶图的定向图

完全偶图是具有二分类（X,Y）的简单偶图，其中X的每个顶点与Y的每个顶点相连，若｜X｜=m,｜Y｜=n，则这样的图记为K_m,n。本文主要研究了Kn,n的定向图。证明了如下结论：对于非负整数a和b，若存在满足每个顶点的入度是a或者是b的一个Kn,n的定向图，则存在非负整数s和t满足方程s+t=2n和as+bt=n2。进一步，对于满足特定条件的非负整数a，b和n，存在K_n,n的定向图使得每个顶点的入度非a即b。     

基于最省刻度尺构造极小优美图的图论方法

[目的]利用最省刻度尺的已有研究成果研究极小优美图的构造方法.[方法]对任意正整数n≥2,在长度是n的无刻度直尺上最少刻多少个刻度,就能度量1-n的所有长度,这就是最省刻度的尺子问题.给定正整数n,存在m个整数组成的集合{a_i},满足0=a₁2<…m=n,使得任意整数s(0≤s≤n)均可表示成该集合中两个元素的差a_j-a_i,则称{a_i}为n上的受限差基.根据极小优美图和受限差基的定义,将极小优美图问题等效为最省刻度尺问题进而得到极小优美图的构造方法.[结果]由n≥5时K_n不是优美图和n≥1时图K₄+K_n,n是优美图的结论,得到了边数是6至82的极小优美图顶点数的上下界;用构造方法给出了图K₃∨K_1,3,n-3e,K_3,n∨K₃-e和K_2,3,n     

关于完全s部整图

F.Harary和A.J.Schwenk(Lecture Notes in Mathematics.Berlin:Springer-Verlag,1974,406:46-51.)提出了整图的概念,即当无向图G的邻接矩阵A的特征值都是整数时,G称为整图.目前,人们已经研究了n类简单整图的性质,并得到了一些有趣的结果.运用线性代数方法证明了两个结论:设r,r1,r2,s是正整数,那么:1)完全s部图K(r,r,…,r)是整图;2)完全2部图K(r1,r2)是整图的充要条件是r1r2为完全平方数.     

一类可图拟阵的二阶圈图的哈密顿性

为研究一般连通拟阵的二阶圈图的哈密顿性,选取完全二部图K_2,n和K_3,n进行讨论,证明这两类圈拟阵的二阶圈图的哈密顿性,并证明K_2,n的圈拟阵的二阶圈图的连通度和泛圈性,对K_2,n,K_3,n的圈拟阵的二阶圈图的一致哈密顿性提出了一个猜想。     

完全图K2n+1的2因子分解

为了解决完全图K_2n+1的2因子分解的问题,通过给出奇阶完全图K₁₃的2因子分解的全过程,阐明了奇阶完全图K _2n+1的2因子分解的具体步骤,解决了完全图的2因子分解问题。     

关于完全3部图的色唯一性

文章设P(G,λ)是图G的色多项式,若对于任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(G≌H),则称图G是色唯一图;通过比较3部图的4色类的划分数证明,如果4≤v+2≤k≤2v,n>(k-1)2/4,则完全3部图K(n,n+v,n+k)是色唯一图。     

5类图的优美性

用构造方法给出图K_2,n-1-3-K₃,K_2,n-2-2-K₃,K_2,n-1-2-K₃,K_2,n-2-K₃和K_2,n-3-P₃的优美标号,并证明这五类图都是优美图.当n≤5时,K_2,n-1-3-K₃,K_2,n-2-2-K₃,K_2,n-1-2-K₃和K_2,n-3-P₃都是极小优美图,并给出对应长度尺子刻度数最少的15组刻度值.     

完全二部图K9,n(9≤n≤92)的点可区别E-全染色

利用反证法、 组合分析法及构造具体染色的方法, 讨论完全二部图K_9,n(9≤n≤92)的点可区别E 全染色问题, 给出K_9,n(9 ≤n≤92) 的最优点可区别E-全染色, 并得到了K_9,n(9≤n≤92)的点可区别E-全色数.     

完全四部图的Seidel多项式及其谱

设G是一个简单无向图,A(G)是图G的(0,1)邻接矩阵.定义S(G)=J-I-2A(G)是图G的Seidel矩阵,SG(λ)=det(λI-S(G))是图G的Seidel特征多项式(本文中简记为Seidel多项式),其中I是单位矩阵,J是全1矩阵.如果SG(λ)的特征值都是整数,则图G被称为是S-整图.本文主要研究完全四部图G=Kn1,n2,n3,n4的Seidel多项式及SG(λ)的特征根,给出了完全四部图Kn1,n2,n3,n4是S-整图的充要条件.     

一类完全多部图的Hamiton性刻画

Gutin证明了在强的半完全二部图中若含有一个由两个圈构成的圈因子,则图是Hamilton图。把此定理推广到无向图中就可得到这样一个结果,即含有一个由两个圈构成的圈因子的完全二部图是Hamilton图。在此基础上,对含有由两个圈构成的圈因子的完全n（n≥3）部图进行了讨论,得出了类似于二部图的结果。     

完全三部图K(n-k,n-v,n)的色唯一性

设P(G,λ)是图G的色多项式,如果任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(GH),则称图G是色唯一图.文献[Lau G C,Peng Y H.Chromatic uniqueness ofcertain complete tripartite graphs.Acta Mathematica Sinica,English Series,2011,27(5):919-926]中提出一个猜想(若k≥v≥2,n≥k2/4+v+1,则完全三部图K(n-k,n-v,n)是色唯一的),并证明了若2≤v≤4,k≥v≥2,n≥k2/4+v+1,则K(n-k,n-v,n)是色唯一的.通过比较三角形子图和无弦四边形子图的个数,证明了若v≥4,k≥2v2+4,n≥(k+2)2/8+3,则K(n-k,n-v,n)是色唯一图。     

完全4-部图的交叉数

用分情况讨论法证明了完全4-部图K_(1,1,1,n)、K_(1,1,2,n)、K_(1,1,3,n)的交叉数分别为Z(3,n)、Z(4,n) (N/2)、Z(5,n) n (N/2)(n≥1).     

完全4-部图的无符号Laplacian整根

文中研究了完全4-部图G=Kn1,n2,n3,n4的特征根,给出了完全4-部图是Q-整图的充分必要条件。     

几个完全二部图去掉一条边的交叉数

用km,n表示完全二部图,用Km,n\e表示完全二部图km,n去掉一条边e,先建立Km,n\e的一个好画法得到其交叉数的上界,再证明这个上界确实是K3,n\e和K4,n\e的交叉数,K3,n\e的交叉数为z(3,n)-[n/2]+1,K4,n\e的交叉数为z(4,n)-[n/2]+1.     

完全K部图的Hosoya指标和Merrifield-Simmons指标极图

图的Hosoya指标和Merrifield-Simmons指标是化学图论中两个重要的拓扑指标.考虑点数为n的完全K部图集合K_(n1),_(n2),…,_(nk),证明了在图集K_(n1),_(n2),…,_(nk)中■具有最小的Hosoya指标和最大的Merrifield-Simmons指标,并且图■在K_(n1),_(n2),…,_(nk)中具有最小的Merrifield-Simmons指标和最大的Hosoya指标,其中n=kq+r,0≤rk.     

完全t部图K(n-k,n-2,n,…,n)的色唯一性

文章介绍了完全t部图K(n-k,n-2,n,…,n)的色唯一性,设P(G,λ)是图G的色多项式,若对于任意与图G的色多项式相等(P(G,λ)=P(H,λ))的图H都与图G同构(G≌H),则称图G是色唯一图,通过比较t部图的t+1色类的划分数和三角形子图的个数证明,如果n>[(k+1)2/4]+1,并且k>2,则完全t部图K(n-k,n-2,n,…,n)是色唯一图。     

禁用{■k+1,K2,l+1}的图α谱半径极值问题

令K_s,t是完全二部图,K_n是完全图,其中s,t和n是正整数.令B_4,l是由l个共享一条边的K₄构成的图,■_l是由B_4,l的所有生成子图构成的集合.本文研究了禁用■的图的最大α-谱半径问题.利用■_k+1和K_2,l+1的结构特点以及基本不等式,在具有n个顶点、最大度为Δ且禁用■的连通图中,获得了α-谱半径的上界,且刻画了达到上界的极值图.相应地,在具有n个顶点、最大度为Δ且禁用■_k+1或K_2,l+1的连通图中,得到了α-谱半径的上界.