COMPLETE MULTIPARTITE DECOMPOSITIONS OF COMPLETE GRAPHS AND COMPLETE n-PARTITE GRAPHS

In this paper,a new concept of an optimal complete multipartite decomposition of type 1 (type 2) of a complete n-partite graph Q n is proposed and another new concept of a normal complete multipartite decomposition of K n is introduced.It is showed that an optimal complete multipartite decomposition of type 1 of K n is a normal complete multipartite decomposition.As for any complete multipartite decomposition of K n,there is a derived complete multipartite decomposition for Q n.It is also showed that any optimal complete multipartite decomposition of type 1 of Q n is a derived decomposition of an optimal complete multipartite decomposition of type 1 of K n.Besides,some structural properties of an optimal complete multipartite decomposition of type 1 of K n are given.

完全图K_n分解成五个顶点的星和圈

讨论了完全图Kn分解成五个顶点的星和圈的存在性,给出完全图Kn存在{S5,C5}-强制分解的充要条件是n≥9.以及完全图Kn存在{S5,C5}-分解的充要条件是n≥5(n≠6,7).

Fubini定理公式数计数和齘(n,k)卷积公式

组合数学中,Catalan数有显式公式,Fubini定理公式数无显式公式,本文利用完全图Kn 的k 个分支的完全分支覆盖的个数N(Kn,k)=S(n,k)(第二类Stirling数)和卷积公式,作者将导出Fubini定理的公式数的显式公式,此外获得完全i 部图所有个数基数公式,本文中提出(n,k)概念,并讨论(n,k)的组合卷积公式,最后证明(n)=∑nk=1(n,k)与Fubini公式数之间的关系等式.

Fubini定理公式数计数和φ(n,k)卷积公式

组合数学中,Catalan数有显式公式,Fibini定理公式数无显式公式,本文利用完全图Kn的k个分支的完全分支覆盖的个数N(Knk)=S(n,k)(第二类Stirling数)和卷积公式,作者将导出Fibini定理的公式数的显式公式,此外获得完全i-部图所有个数计数公式,本文中提出φ(n,k)概念,并讨论φ(n,k)的组合卷积公式,最后证明φ(n)=sumfork=1ton(1/k)φ(n,k)与Fibini公式数之间的关系等式。

完全二部图的超k-Steiner Wiener指数

文章利用Hosoya多项式和组合恒等式给出了完全二部图Km,n的超k-Steiner Wiener指数的计算公式.

完全图K_(n)的{P_(5),C_(5)}分解

图分解问题已在很多邻域中得到了广泛的应用。用P_(5)表示5个顶点的路,C_(5)表示5个顶点的圈,本研究讨论了完全图Kn分解成5个顶点的路P5和圈C_(5)的存在性,给出完全图Kn存在{P5,C_(5)}-强制分解的充分必要条件是n≥7(n≠8),以及完全图Kn存在{P5,C_(5)}-分解的充分必要条件是n≥5(n≠6)。

广义图K(n,m)的点强全色数

图G(V,E)的一个正常k-全染色σ称为G(V,E)的一个k-点强全染色,当且仅当v∈V(G),N[v]中的元素着不同颜色,其中N[v]={u vu∈V(G)}∪{v};并且χvTs(G)=m in{k存在G的一个k-点强全染色}称为G的点强全色数.本文确定了完全图Kn的广义图K(n,m)和乘积图Lm×Kn的点强全色数.

完全图K_n的{P_4,S_4,C_4}-分解

讨论完全图Kn分解成4个顶点的路、星和圈的存在性.给出完全图K_n存在{C_4,S_4},{P_4,C_4},{P_4,S_4},{P_4,S_4,C_4}分解以及强制分解的充要条件.

完全图K_n和完全多部图K_n(t)的｛C_3,S_4｝-强制分解

本文给出完全图Kn 和完全多部图Kn(t)存在｛C3 ,S4｝

完全四部图K_(n,n,n,n)(n为偶数)的竞赛数

本文利用ECC来给出关于完全四部图Kn,n,n,n(n为偶数)的竞赛数的一些结果:k(Kn,n,n,n){=2,当n=2;≤n2-7n/2+7,当n=2m+2(m=1,2,…).

完全图K_n中边不重的3圈数

设完全图Kn 中边不重的 3圈数的最大值为c(n ,3) ,证明了 { (n - 1) (n - 2 )6 }≤c(n ,3)≤ [n[n - 12 ]3 ],当n≡ 1,2 ,3(mod 6 )时 ,c(n ,3) =[n[n - 12 ]3 ],并给出了一个得到Kn 中 { (n - 1) (n - 2 )6 }个边不重的 3圈的方法 ,其中n∈ { 3,4,5 ,… } .

Heilbronn问题初探

解决了ｎ＝９的Ｈｅｉｌｂｒｏｎｎ问题，并建立了一套新的理论，为进一步研究其他情形提供一个有效的方法．

关于完全图K_(n)的{P_4,C_4}-分解

讨论了完全图K_(n)分解成四个顶点的路和圈的存在性,给出完全图K_(n)存在{P_(4),C_(4)}-强制分解的充要条件是n≥5且n≠6.以及完全图K_(n)存在{P_(4),C_(4)}-分解的充要条件是n≥4.

n-可着色图的一个充要条件

本文从完全图K_n出发,递归定义了非n色基本子图,n色同色元和n色异色元等概念,然后,给出了n-可着色图的一个充要条件:图G是n-可着色的当且仅当G不包含非n色基本子图。本文又得到一个结论:G是非n-1色基本子图当且仅当G是n-边临界图,从而给出了n-边临界图的构造。

完全四部图K_(n,n,n,n)(n为奇数)的竞赛数

本文中,我们给出了关于完全四部图Kn,n,n,n(n为奇数)的竞赛数的一些结论:k(Kn,n,n,n)=1,当n=1时;=4,当n=3时;=n2-4n+8,当n=2m+3(m=1,2,…)时。

n-倍图的邻点可区别关联着色

邻点可区别关联着色是使得相邻顶点的颜色集不同的关联着色.本文首先给出了邻点可区别关联着色、倍图及n-倍图的定义,然后研究了路与完全图的倍图及n-倍图的邻点可区别关联色数.

K(n,m)图的边色数

设K(n,0)=Kn,V(Kn)={v_1～0,v_2～0…,v_n～0},分别从v_1～0,v_2～0,…,v_(n-1)～0,出发作长为m的n-1条路v_i～0,v_i～1,…,v_i～m,i=1,2,…,n-1;然后,对j=1,2,…,m,添加边{v_i～jv_k～j|k,i=1,2,…,n-1,且k≠i},这样得到的图用K(n,m)表示.证明了对图K(n,m)当n≥2、m≥1时的边色数为n.

完全五部图K_(n,n,n,n,n)(n≡1,5(mod6))的竞争数

Opsut在1982年给出了任意图G的竞争数小于等于其边团覆盖数的结果。对于完全五部图Kn,n,n,n,n,当n≡1,5(mod6)时,本文首先构造一个极小的边团覆盖并从中得到其边团覆盖数,然后利用边团覆盖和竞争图之间的关系得到了其竞争数的一个新的上界,从而改进了由Opsut给出的完全五部图的上界。

n阶完全图的二染色问题

对七阶完全图的二染色问题进行了初步讨论,得出了一些关于同色三角形个数的结论,并在n阶完全图上做了简单的推广。

4或5阶K_n(t)的图对分解

Abueida及Daven给出了完全图Kn的阶为4或5的图对分解存在的充要条件,作为其结果的推广,就阶为4或5的图对(Fi,Hi),给出了完全多部图Kn(t)的(Fi,Hi)分解存在的充要条件.