优美图Bodendiek猜想的证明

Bodendiek猜想一个圈加一条弦是优美图。已由[1]和[2]给出证明。本文以矩阵为工具,给出该猜想的另一种证明,并证明了该猜想的一种推广。     

关于优美图Bodendiek猜想的一种推广

Bodendiek猜想一个圈加一条弦是优美图。已由[1][2]和[3]给出证明。本文以矩阵为工具,证明了该猜想的一种推广:连结两个顶点的三条独立路所成简单图,在一定条件下是优美的。§1 预备知识首先罗列出有关概念。假如对于简单图G(V,E),Vv∈V,赋予一个非负整数ψ(v),则称图G是标定的。     

K顶边星图的优美性

文[1][2]分别给出了轮图和齿轮图的优美性，本文证明了在齿轮图（n为奇数）每个齿的顶端联结k条长度为1的边所得图是优美的，从而得到文[3]所提猜想的一个结果。     

具有K条顶边齿轮图的优美性

文[1][2]中分别给出了轮图和齿轮图的优美性，本文证明了将n个具有K条边的星图TK的非悬挂点分别与齿轮图n个顶点相联所得图是优美的；从而得到文[3]中所提猜想的一个结果，     

优美图Bodendiek猜想的一种推广

Bodendiek 猜想一个圈加一条弦是优美图.已由[1][2]和[3]给出证明.本文以矩阵为工具,证明了该猜想的一种推广:连结两个顶点的三条独立路所成简单图,在一定条件下是优美的.假如对于简单图 G(V,E)的u∈V,赋以一个非负整数(v),则称图 G 是标定的,(v)称为顶点 v 的标号,|(u)—(v)|称为棱 uv 的标数.定义:若图 G(V,E)有满足下列条件的标号,则称 G 是优美图(graceful graph):     

完备二分图Kl，n的r一冠Ir（Kl，n）的K——优美性

讨论了在文[1]中提出的猜想的m＝l的情形，并得到完备二分图K1,n的r--冠的K--优美性的--一个充要条件。     

优美三角仙人掌图的变形

本文给出了几个结论,且利用所得的结论可得一些不同构的优美三角仙人掌图。从而,部分回答了A.Rosa在[1]之中提出的猜想。     

关于树T13的优美性

在n阶树用0,1,2,…,n-1,不同的n个数对定点标号,使得每一条边的标号也不相同,即{1,2,...,n},我们称这种标号是优美标号.在优美树问题中,文献[3]猜想树是优美树;本文讨论了一类树,用T13表示,并研究了树T13的优美性标号.     

关于树T_3~1的优美性

在n阶树用0,1,2,…,n-1,不同的n个数对定点标号,使得每一条边的标号也不相同,即{1,2,…,n},我们称这种标号是优美标号。在优美树问题中,文献[3]猜想树是优美树;本文讨论了一类树,用T13表示,并研究了树T13的优美性标号。     

两类大龙虾树的优美标号

对于J.C.Bermond提出的“所有龙虾树都优美”的猜想,目前已有不少结果(如[1]、[3]、[4]).本文则对两类大龙虾树给出其优美标号。     

2类优美图的冠的优美标号

优美图是图论中重要的研究课题之一,有着广泛的应用价值和研究前景。但是目前仍然很难从理论上对一般图的优美性进行研究。马克杰猜想:所有优美图的冠都是优美图。这一猜想至今没有被证明或否定。对任何正整数m和n,用构造的方法给出了图I(1-Fm,4)和I(K1,1,1,n)的优美标号,从而证明了I(1-Fm,4)和I(K1,1,1,n)都是优美图。     

一类四角仙人掌图的优美性

证明了仅有一条公共边或有一个公共点的四角仙人掌图的优美性，从侧部分解决了Ａ．Ｒｏｓａ提出的猜想。     

关于一类树的优美性

在n阶树用0,1,2,…,n-1,不同的n个数对顶点标号,使得每一条边的标号也不相同(相关联一对顶点的标号差的绝对值不相同),即{1,2,…,n},称这种标号是优美标号;根据优美图的定义,研究了优美树问题中,Rosa猜想树是优美树;本文研究了一类树T_(k_3)~1,的优美性。     

关于Alavi猜想的一个结果

Alavi在[1]中提出了图的升分解问题．并猜想：设G是星S1．S2．…，Sn的并图，S1有a1条边，n≤a1≤2n-2，∑j-1 ^k ai=(n 1/2)．则G可升分解为星图的并．本文证明了当a1≥n，且a1 1-a1=d(d≤S，1≤i≤k-1)时,猜想的结论成立。它可作为[2]的发展。     

再论图Pn^3的优美性

给出图Pn3的另一种优美标号,证明其图是优美图且是交错图.另外指出文献[1]中的一个错误和给出了相应正确的结果,同时证明了严谦泰,张忠辅给出的标号以及我们改正的标号都是交错的.     

蒲公英图的超边优美标号

1994年,Mitchem和Simoson在研究标号图的问题时,提出了超边优美图的概念。在随后的研究中,一些图被证明具有超边优美性质,同时关于超边优美图的一些猜想也被提出。本文利用递归方法构造了蒲公英图的超边优美标号,并证明了蒲公英图是超边优美图。     

再论图P3n的优美性

给出图P3n的另一种优美标号, 证明其图是优美图且是交错图. 另外指出文献[1]中的一个错误和给出了相应正确的结果, 同时证明了严谦泰, 张忠辅给出的标号以及我们改正的标号都是交错的.     

关于k-优美图一个猜想的证明

二分图是一类有着广泛应用的图,但这类图并不都是优美图,因此需要进一步深入研究它的优美性。本文根据马克杰教授提出的猜想:完备二分图Km,n的冠是k-优美图(m≤n,k≥2),利用构造法证明了当m=1或m=2,k≥2时,猜想成立;当m≥3,k≥(m-2)(n-1)时,猜想成立。拓展了k-优美性的研究范围。     

图的升分解的一些充分条件

A Lavi等人在[1]中定义了图的升分解,并提出猜想:设自然数n≥2,G是星S1,S2,…,Sk的并图,Si含有ai条边,n ≤ ai ≤2n-2,∑ai=((n+1)/2),则G可升分解为星图的并。本文说明n=2时猜想不成立。当猜想中的n≥2修改为n≥3时,并不妨假设 ,本文证明了只要下列条件之一满足时猜想就成立:(1) > n+2K一2,且4(n一K+2)≤2 < +3n一4K+8;(2) ≥n+3K-6且     

一种特殊龙虾树的优美标号

六十年代初,Ringel提出的“所有的树都是优美的”猜想引起了广泛的兴趣。虽然问题迄今还没有完满的结果,但人们或从树的顶点数,或从树的边数,或从树的结构等几个方面,对一些树进行了研究,並获得了一些结果。本文就J.C.Bermond提出的“所有龙虾树都是优美的”猜想,给出一种特殊龙虾树的优美标号。单克云、庄肃钦给出的几个有优美标号的龙虾树是我们的结果的特例。从树的结构上易见。[2]中的几种树都是本文给出的树