W_4 ∨ C_n的交叉数

本文研究了五阶图与圈图的联图交叉数.利用假设法和比较法等方法,得到了W4∨Cn的交叉数为Z(5,n)+n+n2+4,并推广了联图交叉数的结果与方法.     

Wm∨Pn的交叉数

在Klesc M给出的联图W_3 V P_n的交叉数的基础上,继续对联图Wm V Pn（m=4,5）的交叉数cr进行了研究,得到了cr（W3 V Pn）=Z（5,n）＋n＋「n/2＋1」以及cr（W5 V Pn）=Z（6,n）＋n＋3[n/2」＋1,n≥2.     

K_4∨C_n的交叉数

在KlescM给出的完全图K_4∨P_n的交叉数的基础上,得到了cr(K_4∨C_n)=Z(4,n)+n+4,n≥3.特别地,当n=3时,cr(K_4∨C_3)=cr(K_7)=9,由此得到完全图K_7的交叉数另一种证明方法.     

六阶图G与Sn的积图的交叉数

确定图的交叉数是NP．完全问题．目前已确定交叉数的六阶图与星图的笛卡尔积图极少。本文确定了—个六阶图G与星图5k积图的交叉数为Z（6,n）＋2n＋[n/2].     

The nonorientable genus of the join of two cycles

In this paper, we show that the nonorientable genus of Cm ＋ Cn, the join of two cycles Cm and Cn, is equal to [（（m-2）（n-2））/2] if m = 3, n ≡ 1 （mod 2）, or m ≥ 4, n ≥ 4, （m, n） （4, 4）. We determine that the nonorientable genus of C4 ＋C4 is 3, and that the nonorientable genus of C3 ＋Cn is n/2 if n ≡ 0 （mod 2）. Our results show that a minimum nonorientable genus embedding of the complete bipartite graph Km,n cannot be extended to an embedding of the join of two cycles without increasing the genus of the surface.     

Minimum Diameter Orientations of Km∨Kn

For a graph G, let D denote an orientation of G having minimum diameter. Define f（G） =diamD. In this paper, we concentrate on exploring the minimum diameter of Km ∨ Kn（m ≥ 1, n ≥ 1）. Some special cases are known： f（Km ∨ Kn） = ∞, 2, 3, where m = landn ≥ 1, m = 2 or m ≥ 4 andn = 1, m=3 and n = 1, respectively. So we only consider the case when m ≥ 2 and n ≥ 2. The following results are obtained. （1） f（Km ∨ Kn） = 3, where m = 2, 3, n ≥ 2 and m = n = 4. （2） f（Km ∨ Kn） = 2, m where m ≥ 5 andmisodd, 2 ≤ n ≤ （m[m/2]）-m. （3） f（Km ∨ Kn） = 2, whereto ≥ 4 and m≡ 0（rood4）, 2 ≤ n ≤ （m m/2）-（m/2＋1）. （4） ]（Km ∨ Kn） = 2, where m ≥ 6 and m ≡ 2（mod4）, 2 ≤ n ≤ （m m/2）-m/2. （5）/（Km ∨ Kn） = 3, where m ≥ 4, n 〉 （m[m/2]）.     

与直线方程有关的最值问题

（2006年江苏高考第21题）设数列{an}，{bn}，{Cn}，满足：bn=an-an＋2，Cn=an＋2an＋1＋3an＋2（n=1，2，3，…），证明{an}为等差数列的充分必要条件是{Cn}为等差数列且bn≤bn＋1（n=1，2，3，…）     

关于图D(Cn),C2n,C3n的星全色数

图G的一个k-全着色满足G的任何路长为2的点,边着色均不相同.我们称它为G的k-星全着色.图G的全部k-星全着色中最小的k称为图G的星全色数,记为Xn(G).讨论一些圈的星全染色问题,得到了图D(Cn)(n=0(mod 3)和n=0(mod 5)),C2n(n=0(mod 20)和n=0(mod 28))以及C3n(n=0(mod 28)和n=0(mod 36))的星全色数.     

S_m∨P_n与S_m∨C_n的交叉数

本文研究与星图有关的联图的交叉数,得到了对任意的n≥1,当m=3,4,5时,星Sm与路P_n的联图的交叉数;以及对任意的n≥3,当m=3,4时,星S_m与圈C_n的联图的交叉数.     

联图S_5∨C_n的交叉数

两个图G和H的联图,记作G∨H,是指将G中每个点与H中的每个点连边得到的图.本文证明了星图S_5与圈C_n的联图S_5∨C_n的交叉数为Z(6,n)+4[n/2]+3(n≥3),其中Z(m,n)=[m/2][(m-1)/2][n/2][(n-1)/2],m,n为非负整数.     

关于Cm ∨ Cn和Cm ∨ Sn的点可区别边色数

对图G的正常边染色,若满足不同点的点所关联边色集合不同,则称此染色法为点可区别的边染色法,其所用最少染色数称为该图的点可区别边色数.本文得到了Cm∨Cn和Cm∨Sn的点可区别边色数.     

关于Sm∨Sn的边色数和邻强边色数

本文研究了m＋1阶的星Sm和n＋1阶的星Sn的联图Sm∨Sn的边染色和邻强边染色．得到了Sm∨Sn的边色数和邻强边色数。     

7阶循环图C（7，2）Pn的笛卡儿积的交叉数

C（7，2）表示由圈C7（v1v2…v7v1）增加边vivi＋2（i=1，2，…，7，i＋2（mod7））所得的循环图．目前没有有关七阶图与路、星和圈的笛卡尔积交叉数的结果，我们证明了7阶循环图C（7，2）与路R的笛卡儿积的交叉数是8n．     

图Pn∨Km,n的全色数

对两个不交的图G,H,V(G∨H)=V(G)∪V(H),E(G∨H)=E(G)∪E(H)∪{uv u∈V(G),v∈(H)},G∨H称为G和H的联图.本文得到了路Pn与完全二部图Km,n的联图Pn∨Km,n的全色数.     

构造不定方程 求解计数问题

由隔板法或自然数的有序分拆容易得到下面的定理： 定理 不定方程x1＋x2＋…＋xm=n（m,n∈N＋,n〉m〉1）的正整数解的组数为Cn-1^m-1；非负整数解的组数为Cn＋m-1^m-1.     

关于完全t部图K(n1,n2,…,nt)的色唯一性

设P（G，λ）是图G的色多项式，如果对任意使P（G，λ）=P（H，λ）的图H都与G同构，则称G是色唯一图。这里通过比较图的特征子图的个数，讨论了由Koh和Teo在文献[1]中提出的问题（若｜ni-nj｜≤2，1≤i，j≤t且min{n1，n2，…，nt}充分大，K（n1，n2，…，nt）是否为色唯一图？）。证明了，若｜ni—nj｜≤2且t↑∑↑i=1 ni〉t^2/2＋t√t-1，则K（n1，n2，…，nt）是色唯一图；若αi=0或k，t↑∑↑i=1 n＋αi〉t^2k^2/8＋｜tk｜/2√t-1，则K（n＋α1，n＋α2，…，n＋αt）是色唯一图。其条件比文献[4]中的条件较好一些。     

与4/p = 1/(n1) + 1/(n2) + 1/(n3) 相关的素变量均值估计

如果n是正整数,我们用f（n）表示丢番图方程4/p=1/n_1＋1/n_2＋1/n_3的正整数解（n1,n2,n3）的个数.对于素数p,f（p）可以分解为f1（p）＋f2（p）,这里fi（p）（i=1,2）为分母n1,n2,n3中恰有i个能被p整除的解的个数.本文我们将研究关于均值∑p〈xfi（p）,i=1,2,的估计,其中p表示素数.     

六阶图C_6+3K_2与P_n,C_n的联图交叉数

用P_n表示n个点的路,C_n表示长为n的圈,C_6+3K_2表示圈C_6添加三条相邻的边3K_2=C_3得到的图.在Kleitman给出的完全二部图的交叉数cr(K_(6,n))=Z(6,n)的基础上,得到了特殊六阶图C_6+3K_2与路P_n,圈C_n的联图交叉数分别为Z(6,n)+3[n/2]+2与Z(6,n)+3[n/2]+4.     

W5×Sn的交叉数

确定图的交叉数是-个NP一完全问题.目前,对于六阶图与星图笛卡尔积的交叉数知之甚少.收稿证明了W5 X.Sn的交叉数为6[n/2][n-1/2] 2n 3[n/2]([x]表示不超过x的最大整数),并得到了W5的部分子图与Sn笛卡尔积的交叉数.     

图Cn及其r-冠的新的优美标号

研究了关于图的r-冠的优美标号的一个问题,证明了：当n≡0,3（mod 4）时,图Cn及其r-冠是优美图,所给出的新的优美标号不同于现有文献中得到的结果.进而证明了当n≡0（mod 4）时,图Cn及其r-冠也是交错图.