关于算术图的一个猜想

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

算术图的构造方法

本文给出了由简易算术图构造复杂算术图的一些方法，发现了许多典型图类的算术标号。     

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

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

路和圈并图的算术标号

证明了Ｐｎ１∪Ｐｎ２∪…∪Ｐｎｋ及Ｃｎ∪Ｃｍ∪（ｎ≡１（ｍｏｄ２）,ｍ≡４（ｍｏｄ４））是算术图 。     

图Cn∪Pm的算术标号

设Ｃｎ∪Ｐｍ（ｎ≥３，ｍ≥２，ｎ，ｍ∈Ｎ）表示一个圈Ｃｎ和一条与其不相交的路Ｐｍ组成的图，本文证明图Ｃｎ∪Ｐｍ是算术图。     

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

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

两类图的（d，1）-全标号

图G的一个k-（d,1）-全标号是一个映射f：V（G）∪E（G）→{0,1,…,k},使得任意2个相邻的点和相邻的边有不同值,且任一对相关联的点和边的值差的绝对值至少为d．G的（d,1）-全标号数λ^Td（G）定义为G有一个k-（d,1）-全标号的最小的k值,得到了扇图与轮图的（d,1）-全标号数。     

On the Gracefulness of Graph P（6k＋2）^3∪Pn^3

讨论了形如P（6k＋2）^3∪Pn^3非连通并图的优美性,用构造性的方法给出P（6k＋2）^3∪Pn^3的优美标号,并证明P（6k＋2）^3∪Pn^3是交错图。     

轮图的（2，1）-全标号

图G的一个后-（d,1）-全标号是一个映射f：V（G）∪E（G）→{0,1,…,k},使得任意2个相邻的点和相邻的边有不同的值,且任一对相关联的点和边的值的差的绝对值至少为d．G的（d,1）-全标号数λd^T（G）定义为G有一个K-（d,1）-全标号的最小的k值,得到了轮图的（2,1）-全标号．     

独弦圈的算术性

一个（ｐ，ｑ）一图Ｇ被称为（ｋ，ｄ）是一算术的，如果其顶点用不同的非负整数标号，使其边值为一个等差级数ｋ，ｋ＋ｄ，ｋ＋２ｄ，．．．，ｋ＋（ｑ－１）ｄ，其中每条边值是相邻两顶点的标号和，本文证明独弦圈是算术图。     

B.D.Acharya和S.M.Hegde关于算术图一个猜想的证明

B．D．Acharya和S．M．Hcgdc猜想[1]：(1)、如果圈C4t 1是(k,d)的算术图，那么必有k=2td 2r，其中r是某个非负整数；(2)如果圈C4t 3是(k，d)算术图，则k=(2t 1)d 2r，其中r是某个非负整数。本文对以上猜想给出了肯定性证明。     

图St(m)∪Kp,q的k优美性及算术性

对于正整数m,p,q,k∈N⁺(N⁺为正整数集合),给出一类非连通图St(m)∪K_p,q, 论证了当k>1, 且min{p,q}≥2时, 该图是k优美图; 当k>(q-1)d+1(d>1, d∈N⁺)时, 图St(m)∪K_p ,q是(k,d)算术图.     

无三角形图超级-λk性的邻域条件

设k为正整数,G是阶n≥2k的无三角形图。如果G中每一对不相邻的点u,v满足|N(u)∩N(v)|≥k+1,则G是超级-λ_k的,或者G≌K_k+1,n-k-1。这一结果在网络可靠性分析中有一定应用。     

两类非连通图优美性的研究

给出了两类非连通图(K2〖TX-〗∨Cn)∪[DD(]3[]i=1[DD)]St(mi)和(K2〖TX-〗∨C2n+k)∪St(m)∪G(k)n-1(k=1,2), 并证明了如下结论:对自然数n, m, m1, m2, m3, 设s=〖JB(［〗〖SX(〗n〖〗2〖SX)〗〖JB)］〗, n≥9, m1≥s+2, 则图(K2〖TX-〗∨Cn)∪[DD(]3[]i=1[DD)]St(mi)是一个优美图; 对 k=1,2,设n, m≥3, G(k)n-1是一个具有n-1条边的k-优美图,则图(K2〖TX-〗∨C2n+k)∪St(m)∪G(k)n-1是一个优美图。 其中,K2是一个具有2个顶点的完全图,K2〖TX-〗是图K2的补图,K2〖TX-〗∨Cn是图K2和n圈Cn的联图, St(m)是一个具有m+1个顶点的星形树。     

非连通图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∨■)为优美图。     

双圈图的优美性

针对双圈图, 设计一种图的优美性判定算法, 并对17个点内的所有双圈图进行优美性验证, 得到了该范围内所有的优美图和非优美图. 结果表明, 在17个顶点范围内, 除∞ 型双圈图C_(m,n)外, 其余所有双圈图都是优美的, 其中(m+n)(mod 4)={1,2}. 最后给出该类图的非优美证明, 并进一步猜测当顶点数大于17时, 该结论仍成立.     

控制圆点临界图的若干性质

对于图G,如果收缩任意一条边,它的控制数下降,则称图G是圆点临界图.如果粘贴图G中任意两个顶点,它的控制数下降,则称图G是全圆点临界图.证明了对于k-正则图,当k为奇数时不存在2-全圆点临界图;当k为偶数时当且仅当此图为k+2阶图时其为2-全圆点临界图.还对是否存在不含临界点的k-全圆点临界图(k≥4)进行了研究,并得出结论:存在不含临界点的4-全圆点临界图和5-全圆点临界图.     

非连通图C4m-1∪C12m-8∪G的优美标号

讨论了非连通图C4m-1∪C12m-8 ∪G的优美性,证明了当m为任意正整数,G是特征为k且缺k＋6m-3标号值的交错图（6m-3≤k＋6m-3≤｜ E（G）｜）时,非连通图C4m-1∪ C12m-8∪G存在缺标号值k＋1的优美标号,其中,G是具有m个顶点的圈.     

一种用4-圈和8-圈对二分图的划分

证明了如果一个平衡二分图G包含4k个点,k≥2,并且对G中每一对满足x∈V₁,y∈V₂的不相邻顶点x和y成立d(x)+d(y)≥2k+1, 则G包含k-2个4-圈和一个8-圈,并且这k-1个圈点不相交。     

单圈图的边幻和全标号

对于图G(p,q),若存在一个映射f:V(G)∪E(G)→{1,2,…,p+q},使得任意边uv∈E(G),满足f(u)+f(v)+f(uv)=K,K为常数,则图G(p,q)为边幻和图。设计了一种算法对16个点以内的单圈图进行标号,依据得到的结果,找到了两类特殊单圈图的标号规律,定义C_nSymbolQC@〓S_m和C_nΔS_m来刻画此两类特殊单圈图,并给出其相关定理及证明。结果表明,点数小于等于16的所有单圈图均具有边幻和全标号,且其中绝大部分是超级边幻和全标号,从而猜测点数多于16的单圈图也具有边幻和全标号。