关于笛卡尔乘积图的优美性

研究了笛卡尔乘积图Pm×Pn×P1的优美标号算法,并且给出了他们都是优美图的证明,同时推广了笛卡尔乘积图Pm×Pn是优美图的结论.     

关于轮图优美标号的性质

设G=(V(G)),E(G))为p个顶点,q条边的连通简单图,以x和y为端点的边记作(x,y).定义1 称l为G的一个优美标号,如果l是一个单射:l:V(G)→{0,1,…,q}使得对所有边(x,y)∈E(G),由(?)(x,y)=|l(x)-l(y)|所定义的函数是一个—一对应.并称l(x)为顶点x的优美值.     

关于优美图的最近结果

对于一个简单图G=(V,E),若对每一个v∈V,存在一个整l(v),使满足若u≠u则若e′≠e″,则l′(e′)≠l′(e″),这里l′(e)定义为|l(u)-l(v)|,若e=uv。则称G是优美图(graceful graph)。由于优美图在编码、循环设计和通讯网络等方面的应用,又因为大多数的图不是优美图。因此,寻找某些特殊类的图的优美标号,便成为组合理论研究的活跃课题。鉴于     

非连通图G1∪G2及G1∪G2∪K2的优美性

将k-优美图的概念进行了推广，引入了k-l优美图及标号间距的概念，并以此为基础，分别推出了一般情形下判定非连通图G1∪G2及G1∪G2∪K2是优美图的两个充分条件；同时得出了图（C3VK^-n）∪st（m）∪K2是优美图，其中k、l为自然数，l〈k，C3是长为3的圈，Kn为n个顶点的完全图，K^-n是Kn的补图，St（m）表示m＋1个顶点的星形树，C3VK^-n是C3与K^-n的联图．     

一类图优美性的证明

本文给出一种 GL 阵的概念,把若干 GL 阵进行各种运算,所得的 GL 阵对应的图是优美的。从而得到为数众多的一类图,如放射树等,都是优美图。在[2][3]和[4]中,利用 GL 阵还证明了优美图 Bodendiek 猜想及其一种推广。     

关于图P_n~3优美性的研究

在n个顶点的路Pn上,当且仅当两点的距离为3时增加一条边,所得的图称为P3n,本文给出了图P3n(n≥4)的优美标号,从而证明了P3n都是优美图.     

非连通图G_1uG_2及G_1uG_2uK_2的优美性

将k-优美图的概念进行了推广,引入了k～l 优美图及标号间距的概念,并以此为基础, 分别推出了一般情形下判定非连通图G_1 ∪G_2及G_1 ∪G_2 ∪K_2是优美图的两个充分条件;同时得出了图(C_3 ∨(?)_n)∪St(m)∪K_2是优美图,其中k、l 为自然数,l相似文献   

关于图P3n优美性的研究

在n个顶点的路Pn上,当且仅当两点的距离为3时增加一条边,所得的图称为P3n,本文给出了图P3n(n≥4)的优美标号,从而证明了P3n都是优美图.     

一类偶阶图的边优美性

本文讨论了一类偶阶图的边优美性。同时得到了完全图是边优美图的充要条件。     

图Km,n∪Kp,q的k优美性

路线等在[3]中证明了当k>1,且min{p,q}≥2时,图St(m)∪Kp,q是k优美图.本文论证了当min{m,n,p,q}≥2时,图Km,n∪Kp,q是k优美图.     

P2r,6图的优美性

Kathiresan KM证实$P_{2r,2m-1}$($r,m$皆为任意正整数)是优美的且猜想:除了$(a,b)=(2r-1,4m-2)$外,所有的$P_{a,b}$都是优美的.杨元生证实$P_{2r+1,2m+1}$是优美的,并且证实了当$r\leq7$, $r=9$时的$P_{2r,2m}$是优美的.严谦泰证实$r$为奇数时$P_{2r,2m}$是优美的.采用回溯和分支限界算法搜索到了一个适合于所有$P_{2r,b}$图($r,b$皆为任意正整数)的优美标号,用函数构造法提取其规律并从数学的严格性进行了证明,使得所有的$P_{2r,b}$图($r,b$ 皆为任意正整数)的优美性得到了证实.     

P5,4m的优美性

设u,v是两个固定顶点,用b条内部互不相交且长度均为a的道路连接u、v所得到的图用Pa,b表示。Kathiresan证实P2r,2m-1(r,m均为任意正整数)是优美的,且猜想:除了(a,b)=(2r 1,4s 2)外,所有的Pa,b都是优美的。杨元生已证实P2r 1,2m-1是优美的,本文证明m=2n(2l-1),(0≤n≤4,l∈N)时,P5,4m是优美图。     

积图P_n×P_m的奇优美性和奇强协调性

给出了积图P_n×P_m的奇优美标号和奇强协调标号.     

关于图B（m,n,p）的优美性

在［１］［２］中已证明“除去三种特殊情形，连结两个顶点的三条独立路所成简单图Ｂ（ｍ，ｎ，ｐ）是优美图”，并猜想：对除去的三种情形，Ｂ（ｍ，ｎ，ｐ）也是优美的。本文证实了上术猜想。这样一来，也就证明了［３］中的猜想：有－ｈ－链弦的圈是优美的（ｈ≥２）。     

联图$K_5+P_n$的交叉数

A join graph denoted by G + H,is illustrated by connecting each vertex of graph G to each vertex of graph H.In this paper,we prove the crossing number of join product of K_5 + P_n is Z(5,n) + 2 n + [n/2] + 4 for n ≥ 2.     

Cayley图的边Hamilton性

设Ｘ是有限群Ｇ的一个生成集．Ｃａｙ（Ｘ：Ｇ）表示生成集为Ｘ的Ｇ上的Ｃａｒｌｅｙ图，其顶点集为Ｇ，其边集为所有无序对［ａ，ｂ］组成的集合，其中ａ，ｂ∈Ｇ，ａ－１ｂ∈Ｘ∪Ｘ－１（Ｘ－１＝｛ｘ－１｜ｘ∈Ｘ｝）．若图的每条边都在的Ｈａｍｉｌｔｏｎ圈上，则称图是边－Ｈａｍｉｌｔｏｎ图．本文证明了：当Ｇ为ｐ－群或Ｈａｍｉｌｔｏｎ群时，若Ｘ含有Ｇ的中心元，则Ｃａｙ（Ｘ：Ｇ）是边－Ｈａｍｉｌｔｏｎ图．     

轮图的广义Mycielski图的邻强边色数

设图 G(V,E)为简单图 ,V(Mn(G) ) |{ v0 1,v0 2 ,… ,v0 p;v11,v12 ,… ,v1p,… ,vn1,vn2 ,… ,vnp}E(Mn(G) ) =E(G)∪ { vijv(i+ 1) k|v0 jv0 k ∈ E(G) ,1≤ j,k≤ p ,i =0 ,1,… ,n - 1}称 Mn(G)为 G的 n广义 Mycielski图 ,n为自然数 .本文得到了轮的广义 Mycielski图的临强边色数 .