关于算术图的一个猜想

一个(p,q)—图G被称为是(k,d)—算术的,如果它所有顶点可以被分配到不同的非负整数,使得它的边值可以排列成算术级数k,k+d,k+2d,…,k+(q-1)d,其中一条边的值是分配到它的两个端点的数的和。一个图G被称为是算术的,如果存在两个正整数k和d使得它是(k,d)—算术的。本文证明了Acharya和Hegde提出的下述猜想:对任意正整数n≥5,K不是算术图。     

仅有两个数字恰好各出现两次的图序列

如果非负整数不增序列d=(d1,d2,…,dn)中仅有k个数字恰好各出现t次,其它数字彼此不等,且d为图序列,则称d为G(k,t)图序列.本文讨论了G(2,2)图序列,得到非负整数不增序列d=(d1,d2,…,dn)为G(2,2)图序列的充要条件.     

关于唯一r-偶泛圈图

设r≥4且r是偶整数．阶为2n的偶图G被称为唯一r-偶泛圈图，如果对每个偶整数t，r≤t≤2n，G恰含一个长为t的圈，且G不含长小于，的圈．若G是唯一r-偶泛圈圈，则称G是r-UB-图．证明了恰好存在6个外可平面的r-UB-图和对m≤3恰好存在12个阶为2n和边数为2n＋m的r－UB－图．     

关于图的算术标号

一个（p,q）-图G称为是（k,d）-算术的,若它的顶点可标以不同非负整数,使得它的边的赋值（由它的端点标号之和得到）能排成算术级数k,k＋d,k＋2d,…,k＋（q-1）d.本文综述了算术图的有关结果.     

图C4∪St(m)的k优美性及算术性

给出一类非连通图C4∪St(m). 论证当k>1(k∈N)时, 该图是k优美图; 当k>d+1(d>1, d∈N)时, 图C4∪St(m)是(k,d)算术图.     

有圈二部图覆盖的一个结果

H.Wang猜想,对于任意整数k≥2,存在N(k)使得二部图G=(V1,V2,E)中,V1=V2=n≥N(k),且对于G中任意一对不相邻的顶点x∈V1,y∈V2,有d(x)+d(y)≥n+k,那么,对于G中任意k个独立边e1,e2,e3,…,ek,存在顶点不重的k个圈C1,C2,…,Ck,使得ei∈E(Ci),i∈{1,2,…,k}和V(C1∪C2∪…∪Ck)=V(G).H.Wang及J.A.Bondy对k=2,3时证明了猜想成立,本文对k=4证明了猜想的正确性.     

围长不小于r的2圈分布图的最大边数

阶为 n的图 G的圈长分布是序列 ( c1,c2 ,…cn) ,其中 ci 是 G中长为 i的圈的数目 ,图 G的圈长分布满足 c1=c2 =… =cr- 1=0且对 i=r,r 1 ,… ,n有 ci≤ 2 ,∑ni=rci>0 ,则称图 G是围长不小于 r的 2圈分布图 ,用 fr( n,2 )表示阶为 n的围长不小于 r的 2圈分布图的最大可能的边数 .证明了对每个整数 n≥ r 2 ,有fr( n,2 )≥ n 2 k -2 r 2 4n -2 4k2 8k 4r2 -1 2 r 5,其中 k=[( 5 6 0 n 6 0 ( r2 -3 r) 85) / 3 0 ],这里 [x]表示不超过 x的最大整数 .     

C_(2j+1)∪C_(2k)类与P_n~k类调和图

证明了 Seoud等当 k≥ 3时 C3 与 C2 k的不相交并 C3 ∪ C2 k为调和图的猜想 ,并扩展该结果 ,证明了 C5 ∪ C2 k( k≥ 2 )是调和图 ;给出猜想 C2 j+ 1 ∪ C2 k( j≥ 1,k≥ 2且 ( j,k)≠ ( 1,2 ) )是调和图 .证明了幂图 P4n( 8≤ n≤ 17)与 P5 n( 14≤ n≤ 17)是调和图 ,否定了 Seoud等关于当且仅当 1≤ k≤ 3时 Pkn( 1≤ k≤ n -1)是调和图的猜想 .给出了相反的猜想 :当 n≥ n0 ( k)时 Pkn是调和图 ( n0 ( k)为依赖于 k的足够大的整数 )     

关于（K，d）－算术图的两个猜想

文献［１］中猜想：（１）若Ｃ４ｔ＋１是（Ｋ，ｄ）－算术图，则有非负整数ｒ，使得Ｋ＝２ｄｔ＋２ｒ；（２）如果Ｃ４ｔ＋３是（Ｋ，ｄ）－算术图，则有非负整数ｒ，使得Ｋ＝（２ｔ＋１）ｄ＋２ｒ。本文证明了这两个猜想均是正确的     

由圈得到的一类优美图

刘瑞元在〔1〕中证明一个 n(n≥6)个顶点的圈增加两条弦所得图优美,本文证明圈增加若干弦所得图优美.定理具有4k+r 个顶点的圈 C(r=0,1,2,3),可增加 t(1≤t≤2k)条弦,使所得图 C′优美.定理的证明分4种情况:r=0,l,2,3.引理1 具有4k 个顶点的圈 C,可加上t(0≤t≤2k)条弦,使所得图 C′优美。引理2 具有4k+1个顶点的圈 C,可增加t(1≤t≤2k)条弦,使所得图 C′优美.引理3 具有4k+2个顶点的圈 C,可增加t(1≤t≤2k)条弦,使所得图 C′优美.引理4 具有4k+3个顶点的圈 C,可增加t(1≤t≤2k+1)条弦,使所得图 C′优美.     

图的边添加和减少

用P（t,d）（或者C（t,d））表示从一条长为d的简单路（或者简单圈）通过添加t条边后得到图的最小直径.证明了：如果t和d满足条件t≥4且t＋4≤d≤t＋7,或者t=4且d=10k＋1（k≥1）,那么P（t,d）=[d-2D＋1]＋1.对某些t和d,确定了C（t,d）的值和最好下界,部分地解决了Schoone等的猜想[J.GraphTheory,1987,11：409-427].     

广义Pell数列中的平方类

设t是大于1的整数，U={Uk}k=0是参数为t的广义Pell数列。本文证明了：如果t=2dr^2，(t √t^2 1)^d (t-√t^2 1)^d=4s^2，其中d，r，s是正整数，而且d是无平方因子正奇数，则U恰有一个平方类{Ud，U2d)；否则，U没有平方类。     

变更图的边添加

证明了:对任何整数t≥6和d≥2,从一条长为d的简单路通过添加t条边后得到的图的最小直径上界为[d-2/t 1] 2,如果d∈J'(t,k)={2k(t 1) 1,2k(t 1) 2,2k(t 1)-t 1}∪{2k(t 1)-t h:h=6,7,…,t};其他情形为[d-2/t 1] 1.这个证明改进了已知结果,而且[d-2/t 1] 1是最好的上界.     

关于完全三部图K(n-k,n,n+k)的色性

设Ｇ为简单图,Ｐ（Ｇ,λ）的色多项式,若对任意简单图Ｈ满足Ｐ（Ｈ,λ）＝Ｐ（Ｇ,λ）,都有Ｈ与Ｇ同构,则称Ｇ是色唯一图,设Ｋ（ｍ,ｎ,ｒ）表示完全三部图,证明了：（１）对任意非负整数ｋ,若ｎ≥２√－３ｋ／３＋ｋ＾２,则Ｋ（ｎ－ｋ,ｎ,ｎ＋ｋ）是色唯一图。（２）若ｎ≥９,则Ｋ（ｎ－３,ｎ,ｎ＋３）是色唯一图。     

关于Diophantine方程x~3±1=Dy~2

利用数论中的同余,勒让德符号的性质及其它一些方法,研究丢番图方程x3±1=Dy2(D=D1p,D是无平方因子的正整数,其中D1是不能被3或6k+1之形的素数整除的正整数,p=3(12r+7)(12r+8)+1,r是正整数)的解的情况。证明了当D1≡7(mod12)时,方程x3+1=Dy2无正整数解;当D1≡5,8(mod12)时,方程x3-1=Dy2无正整数解。     

星图网络的定向图

主要研究了星图网络Sn的定向图.证明了如下结论:对于非负整数a和b,若存在满足每个顶点的入度或者是a或者是b的一个Sn的定向图,则存在非负整数s和t满足方程s+t=n!和as+bt=(n-1)/2.进一步,对于满足特定条件的非负整数a,b和n,存在Sn的定向图使得每个顶点的入度或者是a或者是b.     

恰有2个内度的2维Torus网络的定向图

设G是一个简单图且D是G的一个定向图.若对D中任意顶点x,d-(x)=a或b,则称G是[a,b]可实现的.主要研究了2维Torus网络中[a,b]可实现的充要条件.设H=Torus(p,k)是一个2维Torus网络,其中p和k是2个不小于3且奇偶性相同的正整数.设0≤a,b≤4,则H是[a,b]可实现的当且仅当存在非负整数s和t使得s+t=kp且as+bt=2kp.     

完全三部图K（n,n,n＋k）的色性

设Ｇ为简单图,Ｐ（Ｇ,λ）为Ｇ的色多项式。若对任意简单图Ｈ满足Ｐ（Ｈ,λ）＝Ｐ（Ｇ,λ）,都有Ｈ与Ｇ同构,则称Ｇ是色唯一图,设Ｋ（ｍ,ｎ,ｒ）表示完全三部图。证明了（１）对任意非负整数ｋ,若ｎ≥ｋ＋ｋ＾２／３,则Ｋ（ｎ,ｎ,ｎ＋ｋ）是色唯;（２）若ｎ≥４,则Ｋ（ｎ,ｎ,ｎ＋４）是色唯一图。     

关于连续数方程注记

本文用初等方法证明了,当ｎ,ｘ ,ｒ 是正整数且ｒ ＞ ３ ,ｄ ＝ ２ｓ＋ ２ ,整数Ｓ≥０ ,ｇｃｄ（ ｘ,ｄ） ＝ １ ,丢番图方程ｎ－１ｋ＝ ０（ｘ ＋ ｄｋ）ｒ ＝ （ｘ ＋ ｄｎ）ｒ 无整数解。