二色有向图及二色有向自补图的计数与构造

通过构造一种新的群,解决了二色有向图及二色有向自补图的计数问题.获得了有 m 个顶点的一种颜色和 n 个顶点的另一种颜色的二色有向图的计数发生函数B_(m,n)(x)及二色有向自补图的数目分别是 B_(m,n)(x)=Z(S_m*S_n;1+x)和 Z(S_m*S_n;0,2,0,2,…).并构造出 m=n=2的全部76个二色有向图及全部12个二色有向自补图.     

阶数不超过8的标定自补图的计数

标定自补图的计数问题是“组合计数”理论中的难题.本文通过构造出的阶数≤8的全部自补图,计算出每一个自补图的自同构群,获得了顶点数分别为4,5和8的标定自补图的数目分别是12,72和112140.     

关于互补平面图的A■iyama-Harary问题的一个注记(英文)

纠正了[1,2]中的几个错误。设G是一个简单图,■表示G的补图。若G与■均为平面图,则称G对应于一个CPGP。当n=7时,CPGP的总数为300;当n=8时,CPGP的总数为1101。因此,所有互补平面图偶(CPGP)的总数为1491。     

等差数列的两个充要条件

我们知道,如果{a_n}为等差数列(以下简记为A·P),那么它的通项和前n项和分别是: a_n=a_1 (n-1)d ① S_n=na_1 n(n-1)d/2 ② 整理,得 a_n=d_n (a_1-d) ③ S_n=d/2n~2 (a_1-d/2)n ④ ③、④二式表明:当d≠0时,A·P的a_n是n的一次式,S_n是n的二次式;当d=0时,A·P的a_n是常数,S_n是n的一次式。 现在的问题是:如果一个数列的通项a_n=kn b(k,b为常数),那么这个数列是否是A·P?如果前n项和S_n=pn~2 q~n r,这个数列是否是A·P?下面的两个定理分别解决了这个问题。 定理1 数列{a_n}为A·P的充要条件是:a_n=kn b(其中k,b是常数)。     

方格偶图Bm×n中的圈数

设Bm×n是具有m×n个顶点的方格偶图，g(m，n)表示图Bm×n中不同圈的数目.证明了g(2，n)=n(n+1)/2，g(3，n)/2=[(1+     

关于CmUnK_2的对角Ramsey数

本文所讨论的图都是有限、无向简单图,记为G=(V,E),其中V、E分別表示图G的顶点集、边集。K_n表示n个顶点的完全图,K_(n,n)表示每部有n个顶点的完全两部图;Pn表示n个顶点的路;Cm表示m个顶点的圈,当m为奇(偶)数时,称Cm为奇(偶圈;CmUnK_2表示顶点数为m 2n的图,其中m个点组成圈Cm,余下2n个点组成nK_2(n个K_2的并图)。     

偶圈的Turán数和Wenger图

设G是一个图,G的Turán数记作ex(n;G),是指阶数为n的不含G作为子图的图的最大边数.根据Erds在1965年给出的偶圈C2m的Turán数ex(n;C2m)的上界10mn1 1/m和Wenger在1991年构造的偶图Hm(q),并由这种图得到的ex(n;C2m)(m=2,3,5)的下界cn1 1/m(其中c为一个与n无关的常数),可以知道,当n→ ∞时,ex(n;C2m)=O(n1 1/m)(m=2,3,5).n1 1/m就是ex(n;C2m)的准确阶.给出了Wenger图Hm(q)的一些一般性质,并分别构造了Hm(q)中长为8的圈(m≥4)和Hm(q)中长为12的圈(m≥6),从而证明了不可能由图Hm(q)得到ex(n;C2m)的所有准确阶.     

n元一次不定方程的一种解法

不定方程a_1X_1+a_2X_2+…+a_nx_n=b (n≥2,6,a_i∈Z,i=1,2…n),当n=2时可用公式求解,但当n>2时目前还没有求解公式.本文用代数方法解决了这一问题。     

偶圈的Turán数和Wenger图

设G是一个图,G的Tur(a)n数记作ex(n;G),是指阶数为n的不含G作为子图的图的最大边数.根据Erd(o)s在1965年给出的偶圈C2m的Tur(a)n数ex(n;C2m)的上界10mn1+1/m和Wenger在1991年构造的偶图Hm(q),并由这种图得到的ex(n;C2m)(m=2,3,5)的下界cn1+1/m(其中c为一个与n无关的常数),可以知道,当n→+∞时,ex(n;C2m)=O(n1+1/m)(m=2,3,5).n1+1/m就是ex(n;C2m)的准确阶.给出了Wenger图Hm(q)的一些一般性质,并分别构造了Hm(q)中长为8的圈(m≥4)和Hm(q)中长为12的圈(m≥6), 从而证明了不可能由图Hm(q)得到ex(n;C2m)的所有准确阶.     

具有多个强正则自补图的最小阶数

本文应用两个不同构的13阶强正则自补图,解决了Kotzig在1979年提出尚未解决的问题:“至少存在两个非同构的4k 1个顶点的强正则自补图集中,其最小整数k是什么?”,获得了最小整数k=3,并且否定了Kotzig在这个问题上所获得的结果.     

Hamilton二部图的一个充分条件

证明了当设G=(X,Y;E)是连通二部图,｜X｜=｜Y｜=n!5,且δ(G)≥2,若NC2≥n-1,则G是Hamilton图。     

二分图中k-因子存在的两个充分条件

设G=(X,Y;E)为二分图,其中| X |=| Y |=n为整数.证明了若     

偶图的边共色数

给出了f（Δ）≥Δ条件下偶图的边共色数及偶图边共色数的一种算法,并确定了k-正则偶图,Kp1,p2及Kp1,p2,…,pk的边共色数.     

二部图中含指定顶点的独立4-圈

G的一个子图集合称为相互独立的或顶点不相交的,如果它们中的任何两个子图在G中没有公共顶点。对于二部图,给出了k个含指定顶点的独立4-圈的最小度条件。     

关于二部图圈的一个结果

设G=（X,Y;E）是连通二部图,｜X｜=n≥5,｜Y｜=n-δ,若NC2≥n-δ,则图G的周长C（G）≥2（n-δ）。进而G有控制圈。     

关于平衡二部图Hamilton性的一个Fan－型条件

文中证明了２－连通平衡二部图中Ｈａｍｉｌｔｏｎ圈存在性的一个Ｆａｎ一型充分条件     

关于几个带宽定理的讨论

指出了不等式B(G)≥p(G)-1/2{2-[(2p(G)-1)~2-8q(G)]~(1/2)}的错误,给出了正确结论;改进了不等式B(G)≥[Δ(G)/2)。用较简单方法证明了B(G)+B(G)≥p(G)-2。     

非连通图G+e∪H_(k-1)的优美性

证明了当k≥2时,非连通图G+e∪Hk-1是优美图,其中G是特征为k的平衡二分图,Hk-1是任意一个k-1条边的优美图.     

非连通图12126C（r,0，r,0,？，r,0）k,4？F的优美标号

讨论了非连通图C12（r1,0,r2,0,…,r6,0）∪Fk,4的优美性,证明了a,k,ri（i=1,2,…,6）,为任意自然数,且当r5=r6=0, k=3,r6=a,r5≥2-a,k=4;r6≥4,k=5时,非连通图C12（r1,0,r2,0,…,r6,0）∪Fk,4是交错图。其中C12（r1,0,r2,0,…,r6,0）∪Fk,4表示圈C12的（r1,0,r2,0,…,r6,0）-冠,把顺序有一个公共点的k个C4的连通并图记作Fk,4。     

非连通图C_(16)(r_1,0,r_2,0,…,r_8,0)∪F_(k,4)的优美标号

讨论了非连通图C16(r1,0,r2,0,…,r8,0)∪Fk,4的优美性,证明了a,k,ri(i=1,2,…,8)为任意自然数,且当r6=r7=r8=0,k=4;r7+r8=2,k=5;r8=a,r7≥4-a,k=6;r8≥6,k=7时,非连通图C16(r1,0,r2,0,…,r8,0)∪Fk,4是交错图。