W5×Sn的交叉数

轮W5的六个顶点与另外n个顶点联边得到了一类特殊的图Hn．文中先证明了Hn的交叉数为Z（6,n）＋n＋3[n/2],并在此基础上证明了轮W5与星Sn的笛卡尔积的交叉数为Z（6,n）＋2n＋3[2/2].     

W5×Sn的交叉数

轮W5的六个顶点与另外n个顶点联边得到了一类特殊的图Hn．文中先证明了Hn的交叉数为Z（6,n）＋n＋3[n/2],并在此基础上证明了轮W5与星Sn的笛卡尔积的交叉数为Z（6,n）＋2n＋3[2/2].     

几个六阶图与星S_n的笛卡尔积交叉数

分别连结六阶图G1的6个顶点与其它n个顶点,得到一类特殊的图Hn.运用组合方法、归纳思想及反证法证明了Hn的交叉数为Z(6,n)+2「n/2」,并在此基础上证明G1与星K1,n的笛卡尔积的交叉数为Z(6,n)+2「n/2」;另外,证明了含子图S5的其它6个六阶图与星K1,n的笛卡尔积的交叉数都为Z(6,n)+4「n/2」.     

关于六阶图与星的笛卡儿积交叉数

通过在完全图K4的某一条边上增加2个顶点得到一个六阶图F.分别连结F六个顶点与其他n个顶点得到一类特殊的图Hn.证明Hn的交叉数为Z(6,n) n并由此确定且证明FXSn的交叉数为Z(6,n) 2n.     

K5\e×Sn的交叉数

K5\e×Sn表示将完全图K5删除一条边e所得到的图,Sn表示星图K1,n.证明了一类特殊的图Hn的交叉数为Z(5,n)+2n以及笛卡儿积图K5\e×Sn的交叉数为Z(5,n)+4n.     

S4 V Cn的交叉数

将星图S4的每个顶点与Cn每个点相连,得到的图记为S1VCn.本文证明了S1VCn的交叉数为Z(5,n)+2|n/2|+2.     

K_(2,3)∨C_n的交叉数

将完全二部图K_(2,3)的每个顶点与C_n每个点相连,得到的图记为K_(2,3)∨C_n.利用一些完全多部图的交叉数结论,将K_(2,3)∨C_n与K_(2,3,n)比较,证明了K_(2,3)∨C_n的交叉数为Z(5,n)+n+3.     

K2,VCn的交叉数

将完全二部图K2,3的每个顶点与Cn每个点相连,得到的图记为K2,3 VCn.利用一些完全多部图的交叉数结论,将K23VCn与K2,3,n比较,证明了K23VCn的交叉数为Z(5,n)+n+3.     

完全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).     

一个五点图和路的联图的交叉数

计算了一个具体图类Hn的交叉数,然后研究了一个五点图G和Pn路的联图G∨Pn,并用归纳假设法证明了这个五点图和路的联图的交叉数Cr(G∨Pn),即当n≥2时,Cr(G∨Pn)=4 2n n 2-1+n2+1.     

一个六阶图与星的笛卡儿积交叉数

拓展了目前关于星与低阶图的笛卡儿积交叉数的某些结论,确定了1个特殊6-阶图与星K1,n的笛卡儿积交叉数为z(6,n)+4n,并给出了1个有在K2,4,n中加入2条边分别联结K2,4,n中2对n+2度点得到的1个特殊图类Hn的交叉数.     

G7×Sn的交叉数

计算并证明了五阶图G7与星Sn的笛卡尔积交叉数cr(G7×Sn)=Z(5,n)+｜n/2｜,这一结果填补了Mrián Kle(s)(c)关于五阶图与星的笛卡尔积交叉数的一处空白.     

非连通并图的优美标号研究

设图G3是长度为3的圈C3或为含3个顶点的路P3,文章给出了非连通图(G3∨Km)∪Kn,t和(G3∨Km)∪Pn,并证明了对任意正整数m,n,t,如果min{n,t}≤m,则图(G3∨Km)∪Kn,t是优美图;如果2≤n≤2m+1,则图(G3∨Km)∪Pn是优美图;同时证明了对任意正整数m,n,图(G3∨Km)∪St(n)和(G3∨Km)∪W2n+5是优美图.其中,Pn是n个顶点的路,G1∨G2是图G1与G2的联图,Km是m个顶点的完全图,m是Km的补图,Kn,t是具有二分类(X,Y)的完全偶图,且|X|=n,|Y|=t,St(n)是具有n+1个顶点的星形树,Wn是具有n+1个顶点的轮图.     

Gracefulness of disconnected graphs W(k)m∪G

文章证明了对任意自然数n≥1,P≥1,K≥1,当m1=2p+3或2p+4时,图W(k)m1U Kn,p为优美图,其中W(k)m1为由k个轮Wmi(i=1,2,…,k)的中心顶点合并后构成的连通图;当m1≥3,n≥[m1/2]时,非连通图W(k)m1∪St(n)为优美图;对任意自然数P≥1,图W(k)2p2+i∪Gpi为优美图,其中,Gpi表示p条边的i-优美图(i=1,2);对任意自然数n≥1,当m1=2n+5时,图W(k)m1∪(C3VKn)为优美图.     

三类自生数群

本文证明了：末位数字为1，3，7，9（2，4，6，8或5）的n位自生数的集合Gn(Hn或Sn)关于模10^n的乘法*是一个交换群。     

两个5阶图与路及圈的联图的交叉数

详细的讨论了和两个5阶图Gi(i=11,14)有关的联图的交叉数,分别是:Gi+Hn,Gi+Pn和Gi+Cn,其中Hn是由n个孤立点构成的图,Pn和Cn分别是含n个点的路和圈.     

非连通图Wmk∪G的优美性

文章证明了对任意自然数n≥1,p≥1,k≥1,当m1=2p+3或2p+4时,图W(k)m1∪Kn,p为优美图,其中Wm1(k)为由k个轮Wmi(i=1,2,…,k)的中心顶点合并后构成的连通图;当m1≥3,n≥[m1/2]时,非连通图Wm1(k)∪St(n)为优美图;对任意自然数p≥1,图W2p+2+i(k)∪Gip为优美图,其中,Gpi表示p条边的i-优美图(i=1,2);对任意自然数n≥1,当m1=2n+5时,图Wm1(k)∪(C3∨■)为优美图。     

完全立方Halin图的2-距离着色

图G的2-距离着色是正常的顶点着色,并且使G中距离不大于2的任意两个顶点着不同的颜色.图G的2-距离色数是图G的所有2-距离着色中所用色数的最小者,记为χ2d(G).探讨了完全立方Halin图Hn的2-距离着色,并得χ2d(H0)=4,5≤χ2d(Hn)≤6(n≥1).     

NT-HIT(k)公式的存在性

一个合取范式(CNF)公式F是NT-HIT公式,如果F中的任意两个不同的子句中恰有一对互补文字。NT-HIT(k)是公式的子句数与变元数之差为k的NT-HIT公式类。通过构造一个命题公式Hn,m,我们证明了：(1)Hn,m可满足当且仅当存在一个含有n个变元和m个子句的NT-HIT公式。(2)对于NT-HIT(1)中的任意一个公式F,存在一个文字L,L在F中仅出现一次。进一步,我们证明了：对于k≥2,公式Hn,n k是一个不可满足公式。于是,对于k≥2,NT-HIT(k)是一个空集。从而就解决了[1]中的两个公开的问题。     

一类非对称矩阵的最大密度指数集

证明了至少有一对非零对称元但非对称且周期为2的n阶非本原不可约布尔矩阵所成的类的最大密度指数集是(ⅰ)若n(＞3)是偶数,则Hn={2,3,4,5,...,2n-5,2n-4};(ⅱ)若n(＞3)是奇数,则Hn={m∶2≤m≤2n-4且2|m}.