任意 n 个完备二分图的并图的优美性

浅谈稳定完备婚姻的算法及推广话说在1962年，两个数学家David Gale 和Lloyd Shapely 提出了下面的问题：给定若干个男生和同样多的女生，他们每个人都对所有的异性有一个心理的偏好次序。

是否存在一种男女配对组合构成一种稳定的组合关系？这里稳定组合的意思是说，不存在两个非伴侣的异性对彼此的评价比对各自伴侣的评价还要高。

（可以理解，这样的异性太容易红杏出墙了，所以是某种不稳定因素。

）进一步的问题是，在已知每个人对异性的偏好顺序的情况下，怎样求出这种稳定组合方式（如果它存在的话）？你可以理解为这是数学家们替月老问的问题：给定一群孤男寡女，寻找一种牵红线的方式，以确保把红杏扼杀在摇篮里。

1、稳定完备婚姻上面这一问题被称为稳定婚姻问题。

它有很多种可能的解法。

为了让大家相信数学家不是真得如此无聊，我要指出它确确实实是一个地道的组合数学问题，有其特定的数学价值。

当然啦，它也有很多别的背景和应用，比如用来在若干个公司和应聘者之间进行招聘中介……但是数学家们怎么会放过如此八卦的一个名字呢？我们看下面的例题： 某社团中有n 位女士和m 位男士。

假定每位女士按照其对每位男士作为配偶的偏爱程度排名次，无并列。

也就是说，这种排列是纯顺序的，每位女士将这些男士的排列成顺序 1,2,3,… ,n ，类似的,每位男士也对这些女士排列成顺序1，2，3,…，n,我们知道，在这个社团里配对成完备婚姻的方式有n!种。

假定某种婚姻匹配中存在女士A 和 B 及两位男士a 和b,使得i) A 和a 结婚；ii) B 和b 结婚；iii) A 更偏爱b （名次更优先）而非a ；iv) B 更偏爱A 而非B 。

那么，我们认为该完备婚姻是不稳定的。

因为在这种假设下，A 和b 可能会背着别人相伴逃跑，他们都认为，与当前配偶相比每个都更偏爱自己的新伴侣。

如果完备婚姻不是不稳定的，我们则称其为稳定的完备婚姻。

2、稳定完备婚姻的算法2.1 建立模型用二分图来为这个问题建立数学模型。

1999年吉　林　工　业　大　学　自　然　科　学　学　报Vol.29第1期JOURNAL OF J IL IN UNIV ERSITY OF TECHNOLO GY (NATURAL SCIENCES )总第93期收稿日期:1998-07-06毕双艳,女,1944年9月生,副教授两类联图的优美性　毕双艳 唐永林　路　线 李松涛　(长春邮电学院计算机系) (吉林职业师范学院) (吉林工业大学理学院)摘　要　给出了两类联图P 1∨(P 1∨2P n )及st (n )∨T ,论证了这两类图都是优美图,由此推出一些有意义的结论。

关键词　简单图　优美图　联图中图分类号　O15719本文讨论的是简单无向图G (V ,E )。

V (G )和E (G )分别表示图G 的顶点集和边集,|E (G )|表示图G 的边数。

有关术语见文献〔1〕。

定义1〔1〕　对于一个图G (V ,E ),如果对每一个顶点v ∈V ,都存在一个非负整数θ(v )(称为顶点v 的标号),使满足(1)Πu ,v ∈V ,若u ≠v ,则θ(u )≠θ(v )(2)max {θ(v )|v ∈V }=|E |(3)Πe 1,e 2∈E ,若e 1≠e 2,则θ′(e 1)≠θ′(e 2)其中θ′(e )=|θ(u )-θ(v )|,e =uv ,则称G 为优美图(graceful graph )。

θ为G 的优美值(graceful value )或优美标号(graceful labeling )。

定义2〔2〕　设图G 1和G 2不相交,在G 1∪G 2中,把G 1的每一个顶点和G 2的每一个顶点连接起来所得到的图叫做G 1和G 2的联图(join graph ),记作G 1∨G 2。

关于联图的一些研究进展情况见文献〔2〕。

设P n 表示n (n 为自然数)个顶点的简单通路,P 1表示一个顶点的平凡图;把P 1上的顶点与P n 上每一个顶点都通过长度为2的通路连接起来而得到的图记作P 1∨2P n 。

完全图知识点总结一、完全图的基本概念完全图是图论中的一个重要概念，它是一种特殊的图，具有很多独特的性质和特点。

完全图由n个顶点组成，其中任意两个顶点之间都有一条边相连。

完全图通常用Kn来表示，其中n代表顶点的个数。

完全图是一种特殊的简单图，因为任意两个顶点之间都有边，所以在完全图中不存在孤立的顶点或者度为0的顶点。

二、完全图的性质1. 完全图的边数在完全图中，任意两个顶点之间都有边相连，因此完全图的边数可以通过组合数学的知识计算得到。

对于n个顶点的完全图Kn，它的边数可以表示为C(n, 2)，即n个顶点中任取两个顶点相连，共有C(n, 2)条边。

2. 完全图的度完全图中每个顶点的度都是相同的，为n-1。

这是因为在完全图中，任意两个顶点之间都有边相连，所以每个顶点都与其他所有的顶点相邻，因此它的度为n-1。

3. 完全图的邻接矩阵和度矩阵完全图的邻接矩阵是一个n×n的矩阵，其中第i行第j列的元素表示第i个顶点和第j个顶点之间是否有边相连。

在完全图中，邻接矩阵是一个对称矩阵，对角线元素为0，非对角线元素为1。

完全图的度矩阵是一个n×n的矩阵，其中对角线元素为每个顶点的度，非对角线元素为0。

4. 完全图的生成对于完全图Kn，可以使用不同的方法进行生成。

一种方法是从n个顶点开始，逐个添加边直到所有的顶点之间都有边相连。

另一种方法是从n个顶点开始，对于每一对顶点，都添加一条边相连。

5. 完全图的应用完全图在实际生活中有很多应用，例如通信网络中的数据传输、交通规划中的道路建设、社交网络中的人际关系等。

在这些应用中，完全图可以帮助分析网络的拓扑结构、寻找最短路径、评估网络的稳定性等。

三、完全图的相关问题1. 完全图的最大团和最大独立集在完全图中，由于任意两个顶点都相连，因此最大团的大小为n，即完全图本身就是一个最大团。

最大独立集的大小为1，即每个顶点都是一个独立集。

2. 完全图的哈密顿回路和欧拉回路在完全图中，哈密顿回路是指通过所有顶点恰好一次的回路，而欧拉回路是指通过所有边恰好一次的回路。

二分图：二分图是这样的一个图，它的顶点可以分为两个集合X和Y。

所有的边关联的两个顶点中，恰好一个属于集合X，一个属于集合Y。

二分图的匹配：给定一个二分图G，M为G边集的一个子集，如果M满足当中的任意两条边都不依附于同一个顶点，则称M是一个匹配。

二分图的最大匹配:二分图的所有匹配中包含边数最多的匹配称为图的最大匹配。

完美（完备）匹配：如果所有点都在匹配边上，称这个最大匹配是完美匹配。

最佳匹配：如果边上带权的话，找出权和最大的匹配叫做求最佳匹配。

增广路径：也称增广轨或交错轨。

若P是图G中一条连通两个未匹配顶点的路径，并且属最大匹配边集M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广轨。

定义总是抽象的下面通过图来理解它。

图中的线段（2->3, 3->1, 1->4）便是上面所说的p路径，我们假定边（1,3）是以匹配的边，（2,3）（1,4）是未匹配的边，则边（4,1）边（1,3）和边（3,2）在路径p上交替的出现啦，那么p就是相对于M的一条增广轨，这样我们就可以用边1,4 和边2,3 来替换边1,3 那么以匹配的边集数量就可以加1,。

下面给出关于二分图最大匹配的三个定理1:最大匹配数+ 最大独立集= n + m2:二分图的最小覆盖数= 最大匹配数3:最小路径覆盖= 最大独立集最大独立集是指求一个二分图中最大的一个点集，该点集内的点互不相连。

最小顶点覆盖是指在二分图中，用最少的点，让所有的边至少和一个点有关联。

最小路径覆盖是指一个不含圈的有向图G 中，G的一个路径覆盖是一个其结点不相交的路径集合P，图中的每一个结点仅包含于P 中的某一条路径。

路径可以从任意结点开始和结束，且长度也为任意值，包括0.1求解二分图最大匹配的方法：●匈牙利算法（时间复杂度O(nm)）其思想是是通过不断的寻找增广轨实现最大匹配。

●转化为单位容量简单网络的最大流问题(本文不介绍)在二分图的基础上，加入源点s和汇点t，让s与每个X结点连一条边，每个Y结点和t连一条边，所有弧的容量为1。

⼆分图概念及性质 段段续续的看⼆分图已经有些时⽇了。

现在借着周末整理⼀下这么多天对⼆分图的掌握程度。

也好对⼆分图有个整体的认知。

另外，此⽂只针对与⼆分图的⼀些概念和性质，不涉及求最⼤匹配的算法。

好吧，切⼊正题： ⾸先我们抛开⼆分图严谨准确的定义，从⼀个感性的⾓度来认识⼀下什么是⼆分图。

所谓⼆分图，就是能够把图中的定点分成两个X，Y两部分；并且整个图的边只存在于X与Y之间。

就是说，X与Y的内部是不存在边的，否则的话就不是⼆分图了。

举个例⼦：如果把整个⼈类中的男⼈和⼥⼈看成顶点，⼈与⼈之间的恋爱关系（这⾥只讨论异性之间的正常恋爱，同性恋是不被承认的）为边来建⽴图模型的话。

那么这其实就是⼀个⼆分图，其中的男⼈为X部分，⼥⼈为Y部分。

好了，现在我们给出⼆分图严谨的科学定义： 假设图G=（V，E）是⼀个⽆向图，若顶点集 V 可以分解成两个互不相交的⼦集（A，B），并且图中的所有边（i，j）的端点 i，j 分别属于⼦集 A，B 中的元素，则称图 G 是⼀个⼆分图。

为了更好的叙述下⽂，先让我们清楚⼀个概念： 匹配：⽆公共点的边集合。

（形象点就是 X与Y之间的边的个数） 匹配数：边集中边的个数。

最⼤匹配：匹配数最⼤的匹配。

边独⽴集：指图中边集的⼀个⼦集，且该⼦集中的任意两条边之间没有公共点。

（对⽐匹配的概念我们发现，其实边独⽴集和匹配是⼀个概念） 最⼤边独⽴集：包含边数最多的边独⽴集。

（其实就是最⼤匹配，为了⽅便，以后统称最⼤匹配）图1如图1，如果<1,4>是⼀个合法匹配，那么<1,5>就不是⼀个合法的匹配，因为它们有公共点1 。

同样的如果<2,5>是⼀个合法的匹配，那么<2,6>和<3,5>就不是⼀个合法的匹配。

不难看出，其中最⼤匹配是边集：{1， 4， 5}，最⼤匹配数为3 。

独⽴集： 是指图的顶点集的⼀个⼦集，且该⼦集中的任意两个顶点之间不存在边。

・基础数学・完备二分图的冠的k -优美性3刘育兴(赣南师范学院数学与计算机科学学院,江西赣州　341000)摘　要:图的优美性是图的一个重要性质,有广泛的应用.马克杰猜想:完备二分图K m ,n 的冠I (K m ,n )是k -优美图,这里m ,n,k 是任意正整数且m Φn .对于m =2,3,4,5或k >(m -1)n 的情形,利用构造的方法,证明了猜想的正确性.这一结果丰富了优美图理论.关键词:完备二分图;优美图;冠;构造方法中图分类号:O157.5 文献标识码:A 文章编号:1004-8332(2010)03-0011-03图的标号问题是组合数学中一个热门课题.它不仅属于图论领域,也属于设计理论的范畴.图的优美标号是图的标号问题中的一种,有着广泛的应用.图的优美标号主要应用于编码设计、变压器箱设计、射电天文学、晶体结构中原子位置的测定和导弹控制码的设计等方面.研究图的优美性,即寻找图的优美标号.优美图是图论中极有趣的研究课题之一.1966年,A.Rosa 猜想:所有的树都是优美树.这就是著名的优美树猜想.这个猜想至今没有被证明或否定.由于优美图的趣味性和应用性,自1972年S .W.Gol omb 明确给出优美图的定义以来,很快得到了人们的重视,获得了不少研究成果[1-9].1　定义及定理文中所讨论的图G (V,E )都是简单无向图.V (G )和E (G )分别表示G 的顶点集和边集.|E (G )|(或|E |)表示图G 的边数,N +是正整数集合.文中未说明的符号及术语均同文献[1].定义1[1]　对于一个图G (V,E ),若存在单射f:V (G )→{0,1,2,…,|E |-1},使得导出映射f ′(uv )=|f (u )-f (v )|是E (G )→{1,2,3,…,|E |-1}的双射,则称G 为优美图,而f 称为G 的一个优美标号.定义2[1]　对于一个图G (V,E )和任意正整数k,若存在单射f:V (G )→{0,1,2,…,|E |+k -1},使得导出映射f ′(uv )=|f (u )-f (v )|是E (G )→{k,k +1,k +2,…,|E |+k -1}的双射,则称G 为k -优美图,而f 称为G 的一个k -优美标号.特别地,当k =1时,f 为图G 的优美标号.定义3[1]　在图G 的每个顶点上都粘接r 条悬挂边(r ≥1为整数)所得到的图,叫做G 的r -冠.G 的1-冠也称做G 的冠,记作I (G ).文献[1]中马克杰已经证明了下述两个定理,在文献[1]中分别为推论2.4.2和定理4.1.4.定理1　任意优美树的r -冠都是优美的.定理2　完备二分图的冠I (K m ,n )是优美图,这里m ,n,是任意正整数且m Φn .并提出猜想:完备二分图K m ,n 的冠I (K m ,n )是k -优美图,其中k 是大于1的整数.本文证明如下结果.定理3　设K m,n 是任意的完备二分图,m ≤n,k 是大于1的整数,则当m =2,3,4,5时,I (K m,n )是k -优美图.定理4　设K m,n 是任意的完备二分图,m ≤n,k 是大于1的整数,则当k >(m -1)n 时,I (K m,n )是k -优美图.2　定理3的证明图1　图I (K 2,n)图2　图I (K 3,n )2010年 赣南师范学院学报 №.3第三期 Journal of Gannan Nor mal University June .20103收稿日期:2009-09-06 修回日期:2009-10-22　作者简介:刘育兴(1968-),男,江西安福人,赣南师范学院数学与计算机科学学院讲师,主要从事图论研究.定理3的证明　情形1:m=2.如图1所示,定义I(K2,n)的顶点标号f如下:f(s1)=0,f(s2)=n+1;f(x1)=k+3n+1,f(x2)=k+n+1;f(y i)=i,i=1,2,…,n;f(t i)=k+ n+2i,i=1,2,…,n.下面验证:f(v)是图I(Km,n)的一个k-优美标号.(1)不同顶点,其标号不同.由顶点标号f的定义,可知此结论显然成立.(2)边不同,其标号不同.由f导出的边映射f3为:f3(s1x1)=k+3n+1;f3(s1y i)=|f(x1)-f(y i)|=k+3n+1-i,i=1,2,…,n;f3(y i t i)=|f(y i)-f(t i)|=k+n+i,i=1,2,…,n;f3(x2y i)=|f(x2)-f(y i)|=k+n+1-i,i=1,2,…,n;f3(s2x2)=k.因此,f3是E(K2,n)→{k,k+1,k+2,…,k+3n+1}一个双射.由定义知,f是图I(K2,n)的一个优美标号,因此图I(K2,n)是优美图.情形2:m=3.如图2所示,定义I(K3,n)的顶点标号f如下:f(s1)=0,f(s2)=n+1,f(s3)=n+2;f(x1)=k+4n+2,f(x2)=k+3n+2,f(x3)=k+n+2;f(y i)=i,i=1,2,…,n;f(t i)=k+n+2i+1,i=1,2,…,n-1,f(t n)=k+n+1.类似情形1可以验证:f是图I(K3,n)的一个k-优美标号.图3　图I(K4,n)图4　图I(K5,n)情形3:m=4.如图3所示,定义I(K4,n)的顶点标号f如下:f(s1)=1,f(s2)=2,f(s3)=n+3,f(s4)=n+2;f(x1)=k+5n+3,f(x2)=k+4n+1,f(x3)=k+2n+4,f(x4)=k+n+2;f(y1)=0,f(y i)=i+1,i=2,3,…,n;f(t1)=k+5n+1,f(t2)=k+4n+30, f(t3)=k+n+4,f(t4)=k+2n+7,f(t5)=k+2n+9,f(t i)=k+2n+2i,i=6,7,…,n.类似可以验证:f是图I(K4,n)的一个k-优美标号.情形4:m=5.如图4所示,当k=2时,定义I(K5,n)的顶点标号f如下:f(s1)=0,f(s2)=2,f(s3)=n+3,f(s4)=3n+1,f(s5)=n+2;f(x i)=(7-i)n+(7-i),i=1,2,3,4,f(x5)=n+5;f(y1)=1,f(y i)=i+1,i=2,3,…,n;f(t1)=6n+5,f(t2)=4n+5,f(t3)=n+7,f(t i)=n+2i+2,i=5,6,…,n.容易验证:f是图I(K5,n)的一个2-优美标号.当kΕ3时,定义I(K5,n)的顶点标号f如下:子情形1:n为偶数时,f(s1)=0,f(s2)=2,f(s3)=n+4,f(s4)=n+2,f(s5)=n+3;f(x i)=k+(7-i)n+(5-i),i=1,2,3,f(x4)=k+3n,f(x5)=k+n+3;f(y1)=1,f(y i)=i+1,i=2,3,…,n;f(t1)=k+6n+3,f(t2)=k+4n+3,f(t3)=k+3n+4,f(t i)=k+n+2i,i=4,5,…,n-2,f(t n-1)=k+2n+1,f(t n)=k+n+2.21赣南师范学院学报 2010年类似可以验证:f 是图I (K 5,n )的一个k -优美标号.子情形2:n 为奇数时,f (s 1)=0,f (s 2)=2,f (s 3)=n +4,f (s 4)=n +2,f (s 5)=n +3;f (x i )=k +(7-i )n +(5-i ),i =1,2,3,f (x 4)=k +3n,f (x 5)=k +n +3;f (y 1)=1,f (y i )=i +1,i =2,3,…,n;f (t 1)=k +6n +3,f (t 2)=k +4n +3,f (t i )=k +n +2i +1,i =3,4,…,n -3,f (t n -2)=k +4n -1,f (t n -1)=k +2n +1,f (t n )=k +n +2.类似可以验证:f 是图I (K 5,n )的一个k -优美标号.综上所述,当k Ε2时,图I (K 5,n )是k -优美图.作为特例,I (K 2,4),I (K 3,5),I (K 4,5)和I (K 5,6)的一种k -优美标号分别如图5、图6、图7和图8所示.图5　I (K 2,4)的一种优美标号图6　I (K 3,5)的一种优美标号图7　I(K 4,5)的一种优美标号图8　I (K 5,6)的一种优美标号定理4的证明:图9　I (K m ,n )如图9所示,定义I (K m ,n )的顶点标号f 如下:f (s 1)=0,f (s i )=m +(m -i +2)n -i +1,i =2,3,…,m -1,f (s m )=n +1;f (x i )=k +m +(m +2-i )n -1,i =1,2,…,m -1,f (x m )=k +m +n -1;f (y i )=i,i =1,2,…,n;f (t 1)=k +m +m n +n -2,f (t i )=k +m +n +2(i -1),i =2,3,…,n .当k >(m -1)n 时,容易验证:f 是图I (K m ,n )的一个k -优美标号.参考文献:[1]　马克杰.优美图[M ].北京:北京大学出版社,1991:1-158.[2]　毕双艳,李秀芬,路线.图C4∪St (m )的k 优美性及算术性[J ].吉林大学自然科学学报,1999,29(2):19-22.[3]　Jallian J A.A dynam ic survery of graph labeling[J ].The electr onic j ournal of combinat orics,2000(6):1-79.[4]　路线,李秀芬,傅彤.图C8∪St (m )的k 优美性及算术性[J ].长春邮电学院学报,2000,18(4):17-20.[5]　路线,戴红,程小青.图C4∪K m,n 的k 优美性及算术性[J ].吉林工业大学自然科学学报,2000,30(4):40-44.[6]　潘伟,路线.两类非连通图(P2∨K n )∪St (m )及(P2∨K n )∪Tn 的优美性[J ].吉林大学学报(理学版),2003,41(2):152-154.[7]　路线,潘伟,李秀芬.图St (m )∪Kp,q 的k 优美性及算术性[J ].吉林大学学报(理学版),2004,42(3):333-336.[8]　杨元生,容青,徐喜荣.一类优美图[J ].数学研究与评论,2004,24(3):520-524.[9]　刘育兴.图K m,n ∪Kp,q 的k 优美性[J ].大学数学,2007,23(1):90-93.The k 2Graceful ness of the Corona l of Com plete B i partite GraphsL IU Yu 2xing(School of M athe m atics and Co m puter Science,Gannan N or m al U niversity,Ganzhou 341000,China )Abstract:The gracefulness of graphs is an i m portant quality,having wides p read app licati on .Ma kejie guessed that the cor onal of any comp lete bi partite graphis a -graceful graph,where is any positive integer .It is p r oved that this conjecture is true by the construc 2ti on method f or m =2,3,4,5or k >(m -1)n .The result enriches the graceful theory of graphs .Key words:comp lete bi partite graph;graceful graph;cor onal;constructi on method 31第3期 刘育兴　完备二分图的冠的k -优美性。

完全二部图优美性质探索把丽娜;刘倩;刘信生;姚兵【摘要】The bipartite graphs of graph theory and graph labellings are widely used in practical applications,especially recently the graph labelling has been applied to design a new type of graphical password.Firstly, some complete bipartite graphs are constructed by combinatoric and series methods.A new labelling,called edge-odd-magical total labelling,is found and it is proved that the combinatoric complete bipartite graphs admit the edge-odd-magical total labelling.Moreover,series complete bipartite graphs are graceful,or (k ,d)-graceful.%图论的二部图及其标号在实际应用中较多,尤其最近图标号被应用于新型的图形密码设计.首先构造出了组合完全二部图与串联完全二部图,发现了一种叫做奇边魔幻全标号的标号,并给出了组合完全二部图具有奇边魔幻全标号的证明.此外,得出了串联完全二部图是优美图、(k,d)-优美图的结论.【期刊名称】《大连理工大学学报》【年(卷),期】2017(057)006【总页数】6页(P657-662)【关键词】树;完全二部图;优美标号;(k,d)-优美标号【作者】把丽娜;刘倩;刘信生;姚兵【作者单位】西北师范大学数学与统计学院,甘肃兰州 730070;西北师范大学数学与统计学院,甘肃兰州 730070;西北师范大学数学与统计学院,甘肃兰州730070;西北师范大学数学与统计学院,甘肃兰州 730070【正文语种】中文【中图分类】O157.5图的标号设计是图论中具有实际应用背景的研究课题．在图论的研究中，图的第一个标号问题是在20世纪60年代由Ringel[1]提出的，人们根据应用的需要发现了许多关于简单图的标号和猜想．优美图是图的标号理论中十分重要的课题之一．1966年，Rosa在其关于图同构分解问题的研究中提出了关于优美树的猜想，认为“所有的树图都是优美的”[2]．猜想的提出引起了图论研究者的广泛关注，使得包括优美标号、奇优美标号在内的图标号问题研究得到了空前的发展．图的优美标号问题是组合数学研究专题，它不仅属于图论的领域而且在设计理论的范畴．优美图在物流运输、编码理论、雷达、天文学、电路设计等方面都有应用[3]．优美图是图论中的一个重要分支，研究优美图标号问题有助于研究其他类型的图标号问题，定义一个图的顶点标号是图的顶点集到整数集的映射，边标号是图的边集到整数集的映射[4]．根据对映射的不同要求，新的图标号以及新问题不断涌现．经过多年的研究，目前已经有许多关于优美图的研究成果，也导致了一大批新的标号产生．例如：(k,d)-优美标号、边魔幻标号、反魔幻标号、幸福标号及和谐标号等[5]．一个图G是二部图，如果它的顶点集V(G)可以分成两个子集X和Y，且图G中的每一条边都有一个顶点在X中，另一个顶点在Y中，图G可以记作G(X，Y)．如果在二部图G(X，Y)中，X中的每个顶点都与Y中每个顶点相连，则称G(X，Y)为完全二部图，若X中有m个顶点，Y中有n个顶点，则完全二部图G(X，Y)记为Km，n[6]．本文所提到的图都是简单的、无向的并且是有限的，所定义的记号同文献[4]．为叙述方便，把一个有p个顶点和q条边的图叫做(p，q)-图G．设(p，q)-图G有一个映射f：V(G)→[0，q]．记f(V(G))={f(u)：u∈V(G)}，f(E(G))={f(uv)=|f(u)-f(v)|：uv∈E(G)}．本文中用到的[m，n]是指集合{m，m+1，m+2，…，n}，即从m到n的自然数；[s，t]o表示奇数集合{s,s+2，s+4，…，t}，即从s到t的全体奇数；[k，l]e表示偶数集合{k，k+2，k+4，…，l}，即从k到l的全体偶数[7]．文中未给出的符号及定义参见文献[4]．定义1[5-7] 如果(p，q)-图G有一个映射f：V(G)→[0，q]，使得图G中任意两个顶点x、y满足f(x)≠f(y)且定义边uv∈E(G)的标号为f(uv)=|f(u)-f(v)|．当{f(uv)：uv∈E(G)}=[1，q]时，则称f为图G的一个优美标号，图G为优美图．定义2[8] 对于给定的(p，q)-图G，如果存在一个映射f：V(G)→[0，k+(q-1)d]，使得图G中任意两个顶点x、y满足f(x)≠f(y)且边标号集合f(E(G))={k，k+d，k+2d，…，k+(q-1)d}，则称f为图G的一个(k，d)-优美标号，图G为(k，d)-优美图．定义3 对于给定的(p，q)-图G，如果存在一个映射f：V(G)→[0，2q-1]，使得图G中任意两个顶点x、y满足f(x)≠f(y)且定义边uv∈E(G) 的标号为f(uv)=f(u)+f(v)．当{f(uv)：uv∈E(G)}=[1，2q-1]o时，则称f为图G的一个奇边魔幻全标号，图G为奇边魔幻图．图1是组合完全二部图的示意图，它由支架与完全二部图组成，而支架是由顶点a1，a2，…，as依次连接，完全二部图则是由图Gi(i∈[1，s])构成，Gi即为Km，n．其中V(Gi)={ai，bi,t，ci,k|t∈[1，m]，k∈[1，n]，i∈[1，s]}，E(Gi)={aibi,1，bi,tci,k，aiai+1|t∈[1，m]，k∈[1，n]，i∈[1，s]}，再将每个完全二部图Gi中的ai(i∈[1，s])相连．图2是串联完全二部图示意图，它由n个完全二部图依次连接而成，完全二部图则是由图Gi构成，Gi即为Kmi，ni，其中V(Gi)={bi,ti，ci,ki|i∈[1，s]，ti∈[1，mi]，ki∈[1，ni]}，E(Gi)={bi,tici,ki，bi,1ci-1，n|i∈[1，s]，ti∈[1，mi]，ki∈[1，ni]}．定理1 组合完全二部图具有奇边魔幻标号．证明设图G是组合完全二部图，定义图G的一个标号f：令f(b1,1)=0．对i∈[1，s]，t∈[1，m]，k∈[1，n]分情形证明．若m=3，n=4．当s=1时，有f(b1,2)=8， f(b1,3)=16； f(c1,1)=1，f(c1,2)=3， f(c1,3)=5， f(c1,4)=7；f(b1,tc1,k)=2(t-1)n+(2k-1)；f(a1b1,1)=f(b1,3c1,4)+2即结论成立．当s≥2，i为奇数，且m、n为任意数时，边标号如下：f(bi,tci,k)=2(mn+2)(i-1)+2n(t-1)+2k-1；f(aibi,1)=2mn+1+2(mn+2)(i-1)；f(aiai+1)=2mn+3+2(mn+2)(i-1)当i为偶数时，边标号如下：f(bi,tci,k)=2m+7+2(mn-1)-2(k-1)-2(t-1)n+2(mn+2)(i-2)；f(aibi,1)=2mn+5+2(mn+2)(i-2)；f(aiai+1)=2mn+9+2(mn-1)+2(mn+2)(i-2)顶点标号如下：f(a1)=f(a1b1,1)-f(b1,1)；f(ai+1)=f(aiai+1)-f(ai)；f(bi,1)=f(aibi,1)-f(ai)；f(ci,k)=f(bi,1ci,k)-f(bi,1)；f(bi,t)=f(bi,tci,k)-f(ci,k)；f(c1,k)=f(b1,1c1,k)-f(b1,1)；f(b1,t)=f(b1,tc1,k)-f(c1,k)根据上述标号可知，图G的边f(bi,tci,k)、f(aibi,1)、f(aiai+1)标号均为奇数．下证所有边标号在[1，2q-1]o中．在上述的公式中可知，当i=1时，f(b1,1c1,1)=1是最小的，f(b1,1c1,2)=3，f(b1,1c1,3)=5．类推得f(b1,1c1,n)=2n-1，则这n条边的边标号均在[1，2n-1]o中．将f(b1,1c1,1)代入上述式中可得f(b1,2c1,1)=2n+1，f(b1,2c1,2)=2n+3，…，f(b1,2c1,n)=4n-1，则这n条边的边标号被包含在[2n+1，4n-1]o 里．由公式知，f(b1,mc1,1)=2n(m-1)+1，f(b1,mc1,2)=2n(m-1)+3，…，f(b1,mc1,n)=2nm-1，由f(b1,mc1,1)，f(b1,m，c1,2)，…，f(b1,mc1,n)构成的集合为[2n(m-1)+1，2nm-1]o．当i=1时，f(a1b1,1)=2nm+1，f(a1a2)=2nm+3．当i=2时，f(b2,mc2,n)=2nm+7，f(b2,mc2,n-1)=2nm+9，…，f(b2,mc2,1)=2n(m+1)+5，显然n条边的边标号所在的集合为[2nm+7，2n(m+1)+5]o．且f(a2b2,1)=2nm+5．当i=2，t=m-1，k=n时，f(b2,m-1c2,n)=2n(m+1)+7，f(b2,m-1c2,n-1)=2n(m+1)+9，依此类推，得出f(b2,m-1c2,1)=2n(m+2)+5，有{f(b2,m-1c2,n)，f(b2,m-1c2,n-1)，…，f(b2,m-1c2,1)}=[2n(m+1)+7，2n(m+2)+5]o当i=2，t=1，k=n时，f(b2,1c2,n)=4mn-2n+7，f(b2,1c2,n-1)=4mn-2n+9，…，f(b2,1c2,1)=4mn+5，则这n条边的边标号包含在[4mn-2n+7，4mn+5]o中．且f(a2a3)=4mn+7．当i=3时，f(b3,1c3,1)=4mn+9．依次下去标出整个图．若s为奇数，则最大的边标号为f(asbs,1)=2(smn+2s-1)-1；若s为偶数，则最大的边标号为f(bs,1cs,1)=2(smn+2s-1)-1．由上述标号可得f(V(G))→[0，2q-1]，f(E(G))=[1，2q-1]o(其中q=smn+2s-1，表示图的总边数)，f(uv)=f(u)+f(v)．则f是一个奇边魔幻全标号，图G是奇边魔幻图．一个具有奇边魔幻全标号的组合完全二部图在图3中给出．定理2 若图G是串联完全二部图，则图G有优美标号．证明对于完全二部图Km，n，其中X中有m个点，Y中有n个点，则完全二部图Km，n有mn条边，有如图4所示的优美标号．设f为图G的标号．情形1 若存在s个完全二部图，使每个完全二部图中的m为定值，n为变动的，即mi=mj，ni≠nj．下面把s个完全二部图连成一个串联完全二部图，并使得图G 满足优美标号，注意到图G有条边．令f(b1,1)=0．若m=3，n1=4，n2=6，当s=2时，有f(b1,2)=1， f(b1,3)=2； f(c1,1)=31，f(c1,2)=28， f(c1,3)=25， f(c1,4)=22；f(b2,1)=3， f(b2,2)=4， f(b2,3)=5；f(c2,1)=21， f(c2,2)=18， f(c2,3)=15，f(c2,4)=12， f(c2,5)=9， f(c2,6)=6；f(b2,3c2,6)=1， f(b2,2c2,6)=2， f(b2,1c2,6)=3；f(b2,3c2,5)=4， f(b2,2c2,5)=5， f(b2,1c2,5)=6；f(b2,3c2,4)=7， f(b2,2c2,4)=8， f(b2,1c2,4)=9；f(b2,3c2,3)=10， f(b2,2c2,3)=11， f(b2,1c2,3)=12；f(b2,3c2,2)=13， f(b2,2c2,2)=14， f(b2,1c2,2)=15；f(b2,3c2,1)=16， f(b2,2c2,1)=17， f(b2,1c2,1)=18；f(b2,1c1,4)=19； f(b1,3c1,4)=20， f(b1,2c1,4)=21，f(b1,1c1,4)=22； f(b1,3c1,3)=23， f(b1,2c1,3)=24，f(b1,1c1,3)=25； f(b1,3c1,2)=26， f(b1,2c1,2)=27，f(b1,1c1,2)=28； f(b1,3c1,1)=29， f(b1,2c1,1)=30，f(b1,1c1,1)=31可知它满足优美标号的条件．推广到一般情况可按以下过程进行顶点标号：f(b1,1)=0； f(bi,t)=(i-1)m+(t-1)；；f(c1,k1)=mni+(s-1)-m(k1-1)，f(ci,ki)=f(ci-1，n)-1-(ki-1)m可按以下过程进行边标号：f(ci,kibi,t)=f(ci,ki)-f(bi,t)；f(ci,nbi+1，1)=f(ci,n)-f(bi+1，1)．其中i∈[1，s]，t∈[1，m]，ki∈[1，ni]．可知，f(b1,1c1,1)，f(b1,2c1,1)，f(b1,3c1,1)，…，f(b1,mc1,1)分别是q，q-1，q-2，…，q-m+1；f(b1,1c1,2)，f(b1,2c1,2)，f(b1,3c1,2)，…，f(b1,mc1,2)分别等于q-m，q-m-1，q-m-2，…，q-2m+1；依次下去，f(b1,1c1,n1)，f(b1,2c1,n1)，f(b1,3c1,n1)，…，f(b1,mc1,n1)的值是q-(n1-1)m，q-(n1-1)m-1，q-(n1-1)m-2，…，q-n1m+1；…；f(b2,1c1,n1)=q-n1m，f(b2,1c2,1)，f(b2,2c2,1)，f(b2,3c2,1)，…，f(b2,mc2,1)为q-n1m-1，q-n1m-2，q-n1m-3，…，q-(n1+1)m．边b2,1c2,2，b2,2c2,2，b2,3c2,2，…，b2,mc2,2所对应的标号分别为q-(n1+1)m-1，q-(n1+1)m-2，q-(n1+1)m-3，…，q-(n1+2)m；依次下去，f(b2,1c2,n2)，f(b2,2c2,n2)，f(b2,3c2,n2)，…，f(b2,mc2,n2)分别为q-(n1+n2-1)m-1，q-(n1+n2-1)m-2，q-(n1+n2-1)m-3，…，q-(n1+n2)m；f(b2,mc3,1)=q-(n1+n2)m-1，…，f(bs-1，mcs,1)=nsm+1，f(bs,1cs,1)，f(bs,2cs,1)，f(bs,3cs,1)，…，f(bs,mcs,1)与数值nsm，nsm-1，nsm-2，…，(ns-1)m+1对应相等；f(bs,1cs,2)，f(bs,2cs,2)，f(bs,3cs,2)，…，f(bs,mcs,2)的值是(ns-1)m，(ns-1)m-1，(ns-1)m-2，…，(ns-2)m+1；依次下去，f(bs,1cs,ns)，f(bs,2cs,ns)，f(bs,3cs,ns)，…，f(bs,mcs,ns)与m，m-1，m-2，…，1对应相等．情形2 每个完全二部图中的m为变动的，n为定值，即mi≠mj，ni=nj．把s个完全二部图连成一个串联完全二部图，下证图G满足优美标号，其中图G共有条边．对i∈[1，s]，ti∈[1，mi]，k∈[1，n]．若n=3，m1=4，m2=6．当s=2时，有f(b1,1)=0， f(b1,2)=1， f(b1,3)=2，f(b1,4)=3； f(c1,1)=31， f(c1,2)=27，f(c1,3)=23； f(b2,1)=4， f(b2,2)=5，f(b2,3)=6， f(b2,4)=7， f(b2,5)=8，f(b2,6)=9； f(c2,1)=22， f(c2,2)=16，f(c2,3)=10； f(b2,6c2,3)=1， f(b2,5c2,3)=2，f(b2,4c2,3)=3， f(b2,3c2,3)=4， f(b2,2c2,3)=5，f(b2,1c2,3)=6； f(b2,6c2,2)=7， f(b2,5c2,2)=8，f(b2,4c2,2)=9， f(b2,3c2,2)=10， f(b2,2c2,2)=11，f(b2,1c2,2)=12； f(b2,6c2,1)=13， f(b2,5c2,1)=14，f(b2,4c2,1)=15， f(b2,3c2,1)=16， f(b2,2c2,1)=17，f(b2,1c2,1)=18； f(b2,1c1,3)=19； f(b1,4c1,3)=20，f(b1,3c1,3)=21， f(b1,2c1,3)=22， f(b1,1c1,3)=23；f(b1,4c1,2)=24， f(b1,3c1,2)=25， f(b1,2c1,2)=26，f(b1,1c1,2)=27； f(b1,4c1,1)=28， f(b1,3c1,1)=29，f(b1,2c1,1)=30， f(b1,1c1,1)=31可知它满足优美标号的条件．当s>2时，有以下标号过程：f(b1,1)=0， f(b1,t1)=t1-1，f(b2,t2)=n1+(t2-1)，f(b3,t3)=(n1+n2)+(t3-1)，；f(c1,k)=nmi+(s-1)-m1(k-1)，f(c2,1)=f(c1,n)-1，f(c2,k)=f(c2,1)-m2(k-1)，f(ci,1)=f(ci-1，n)-1，f(ci,k)=f(ci,1)-mi(k-1)图G的边标号按以下方程进行：f(ci,kbi,t)=f(ci,k)-f(bi,t)；f(ci,nbi+1，1)=f(ci,n)-f(bi+1，1)有f(b1,1c1,1)，f(b1,2c1,1)，f(b1,3c1,1)，…，f(b1,m1c1,1) 分别等于q，q-1，q-2，…，q-m1+1；边b1,1c1,2，b1,2c1,2，b1,3c1,2，…，b1,mc1,2的标号分别为q-m1，q-m1-1，q-m1-2，…，q-2m1+1；…；f(b1,1c1,n1)，f(b1,2c1,n1)，f(b1,3c1,n1)，…，f(b1,m1c1,n1) 分别为q-(n-1)m1，q-(n-1)m1-1，q-(n-1)m1-2，…，q-nm1+1；依次下去，f(b2,1c1,n)=q-nm1，f(b2,1c2,1)，f(b2,2c2,1)，f(b2,3c2,1)，…，f(b2,m2c2,1)的值为q-nm1-1，q-nm1-2，q-nm1-3，…，q-nm1-m2；f(b2,1c2,2)，f(b2,2c2,2)，f(b2,3c2,2)，…，f(b2,m2c2,2) 分别为q-nm1-m2-1，q-nm1-m2-2，q-nm1-m2-3，…，q-n(m1+m2)；…；f(bs,1cs-1，n)=nms+1，f(bs,1cs,1)，f(bs,2cs,1)，f(bs,3cs,1)，…，f(bs,mscs,1)与nms，nms-1，nms-2，…，(n-1)ms+1对应相等；f(bs,1cs,2)，f(bs,2cs,2)，f(bs,3cs,2)，…，f(bs,mscs,2)分别等于(n-1)ms，(n-1)ms-1，(n-1)ms-2，...，(n-2)ms+1；依次下去，f(bs,1cs,n)，f(bs,2cs,n)，f(bs,3cs,n)，...，f(bs,mcs,n)的值是ms，ms-1，ms-2， (1)情形3 使完全二部图中的m、n均为变动的，即mi≠mj，ni≠nj．下面考察图G是否满足优美标号，图G有条边．对i∈[1，s]，ti∈[1，mi]，ki∈[1，ni]，则有若m1=4，m2=6，n1=3，n2=2．当s=2时，得f(b1,1)=0， f(b1,2)=1， f(b1,3)=2，f(b1,4)=3； f(c1,1)=25， f(c1,2)=21，f(c1,3)=17； f(b2,1)=4， f(b2,2)=5，f(b2,3)=6， f(b2,4)=7， f(b2,5)=8，f(b2,6)=9； f(c2,1)=16， f(c2,2)=10；f(b2,6c2,2)=1， f(b2,5c2,2)=2， f(b2,4c2,2)=3，f(b2,3c2,2)=4， f(b2,2c2,2)=5， f(b2,1c2,2)=6；f(b2,6c2,1)=7， f(b2,5c2,1)=8， f(b2,4c2,1)=9，f(b2,3c2,1)=10， f(b2,2c2,1)=11， f(b2,1c2,1)=12；f(b2,1c1,3)=13； f(b1,4c1,3)=14， f(b1,3c1,3)=15，f(b1,2c1,3)=16， f(b1,1c1,3)=17； f(b1,4c1,2)=18，f(b1,3c1,2)=19， f(b1,2c1,2)=20， f(b1,1c1,2)=21；f(b1,4c1,1)=22， f(b1,3c1,1)=23， f(b1,2c1,1)=24，f(b1,1c1,1)=25可知它满足优美标号的条件．推广到一般情况，可按以下过程进行顶点标号：f(b1,1)=0， f(b1,t1)=t1-1；f(b2,t2)=n1+(t2-1)，f(b3,t3)=n1+n2+(t3-1)，；f(c1,k1)=(mini)+(s-1)-m1(k1-1)；f(c2,1)=f(c1,n1)-1，f(c2,k2)=f(c2,1)-m2(k2-1)，f(ci,1)=f(ci-1，ni-1)-1，f(ci,ki)=f(ci,1)-mi(ki-1)由上述顶点标号可推导出图G的边标号：f(ci,kibi,ti)=f(ci,ki)-f(bi,ti)；f(ci,nibi+1，1)=f(ci,ni)-f(bi+1，1)按上述公式标号可知，第一个完全图的边标号：f(b1,1c1,1)，f(b1,2c1,1)，…，f(b1,m1c1,1)，…，f(b1,m1c1,2)，…，f(b1,m1c1,n1)分别为q，q-1，…，q-m1+1，…，q-2m1+1，…，q-n1m1，f(b2,1c1,n1)=q-n1m1-1，按上面的顺序，串联完全二部图的第二个完全二部图的边标号在[q-(n1m1+n2m2-2，q-n1m1-2)]内，f(b3,1c2,n2)=q-(n1m1+n2m2-3)，…，f(bs,1cs-1，n)=nms+1，f(bs,1cs,1)，f(bs,2cs,1)，f(bs,3cs,1)，…，f(bs,mscs,1)分别为nms，nms-1，nms-2，…，(n-1)ms+1；f(bs,1cs,2)，f(bs,2cs,2)，f(bs,3cs,2)，…，f(bs,mscs,2)为(n-1)ms，(n-1)ms-1，(n-1)ms-2，…，(n-2)ms+1；依次下去，f(bs,1cs-1，ns-1)=nsms+1，第s个完全二部图的边标号在[1，nsms]中．综上，可得标号f满足f：V(G)→[0，q]，f(E(G))=[1，q]，则串联完全二部图G为优美图，f为图G的一个优美标号．推论1 每个串联完全二部图G都有(k，d)-优美标号．证明类似定理1的分类，进行讨论．情形1 完全二部图中的m为定值，n为变动的，即mi=mj，ni≠nj．图G有条边，利用定理1的标号f作图G的一个新标号g，按以下过程进行顶点标号：g(b1,1)=f(b1,1)d， g(bi,t)=f(bi,t)d；g(c1,1)=k+(f(c1,1)-1)d，g(c1,k1)=k+(f(c1,k1)-1)d，g(ci,ki)=(f(ci,ki)-1)+k；g(ci,kibi,t)=g(ci,ki)-g(bi,t)，g(ci,nbi+1，1)=g(ci,n)-g(bi+1，1)其中i∈[1，s]，t∈[1，m]，ki∈[1，ni]．情形2 mi≠mj，ni=nj．把s个完全二部图连成一个串联完全二部图，可计算出图G有条边．g(b1,1)=f(b1,1)d， g(bi,ti)=f(bi,ti)d；g(c1,1)=k+(f(c1,1)-1)d，g(c1,k)=k+(f(c1,k)-1)d，g(ci,k)=(f(ci,k)-1)d+k；g(ci,kbi,ti)=g(ci,k)-g(bi,ti)，g(ci,nbi+1，1)=g(ci,n)-g(bi+1，1)其中i∈[1，s]，ti∈[1，mi]，k∈[1，n]．情形3 mi≠mj，ni≠nj．观察图G是否满足(k，d)-优美标号，图G有条边．g(b1,1)=f(b1,1)d， g(b1,t1)=f(b1,t1)d，g(bi,ti)=f(bi,ti)d；g(c1,1)=(f(c1,1)-1)d+k，g(c1,k1)=(f(c1,k1)-1)d+k；g(c2,1)=(f(c2,1)-1)d+k，g(c2,k2)=(f(c2,k2)-1)d+k，g(ci,1)=(f(ci,1)-1)d+k，g(ci,ki)=(f(ci,ki)-1)d+k；g(ci,kibi,ti)=g(ci,ki)-g(bi,ti)，g(ci,nibi+1，1)=g(ci,ni)-g(bi+1，1)其中i∈[1，s]，ti∈[1，mi]，ki∈[1，ni]．综上，标号g满足g：V(G)→[0，k+(q-1)d] 和f(E(G))={k，k+d，k+2d，…，k+(q-1)d}，则串联完全二部图为(k，d)-优美图，标号g为的它一个(k，d)-优美标号．本文对完全二部图的一些性质做了简要总结，并且在其他标号的基础上研究出一类新的标号：奇边魔幻标号．先对奇边魔幻标号、组合完全二部图、串联完全二部图进行定义，对组合完全二部图、串联完全二部图的性质进行了简单分析，并且证明了组合完全二部图是奇边魔幻图，串联完全二部图是优美图．当然，本文是从最基本的方法出发，显然不够深刻，还需要大量的后续工作来进一步探寻奇边优美标号的性质，以及该标号和这类完全二部图在日常生活中的应用等，从而进一步完善部分完全图的各类标号．【相关文献】[1] RINGEL G. Problem 25 in theory of graphs and its application [C] // FLEDLER M, ed. Proceeding of the 4th International Symposium Smolenice. Prague: Czech Academy of Science, 1963:162-167.[2] ROSA A. On Certain Valuation of Vertices of Graph [M]. New York: Gordon and Breach, 1966:349-355.[3] 李振汉,唐余亮,雷鹰. 基于ZigBee的无线传感器网络的自愈功能[J]. 厦门大学学报(自然科学版), 2012, 51(5):834-838.LI Zhenhan, TANG Yuliang, LEI Ying. Self-healing function based on wireless sensor networks of ZigBee [J]. Journal of Xiamen University (Natural Science), 2012, 51(5):834-838. (in Chinese)[4] BONDY J A, MURTY U S R. Graph Theory with Applications [M]. New York: The Macmillan Press,1976.[5] YAO Bing, YAO Ming, CHEN Xiang′en, et al. Research on edge-growing models related with scale-free small-world networks [J]. Applied Mechanics and Materials, 2013, 513-517:2444-2448.[6] GALLIAN J A. A dynamic survey of graph labelling [J]. The Electronic Journal of Combinatorics, 2000, 6:10-18.[7] LI Lun, ALDERSON D, DOYLE J C, et al. Towards a theory of scale-free graphs: definition,properties, and implications [J]. Internet Mathematics, 2005, 2(4):431-523. [8] ACHARYA B D, HEDGE S M J. Graph theory [J]. Arithmetic Graphs, 1990, 2:275-299.。

树的二分全优美标号
姚明;黄建华;姚兵
【期刊名称】《兰州交通大学学报》
【年(卷),期】2017(036)006
【摘要】一个有q边的连通图G的一个标号是一个映射f,使得图G顶点分配给不同的整数,如果图G的所有边标号集等于{1,2,…,q},则称f是图G的一个优美标号,称G是优美图.图的优美标号可用于解决Rosa分解猜想,这就需要证明每一棵树是优美的,然而它又成为一个未解决的难题.已知树的二分全优美标号可得到一些逼近优美树猜想的结果,因此可考虑一个弱于优美树猜想的猜想:一棵被删除所有叶子后余图恰是一棵毛毛虫树的树T是二分全优美的.树T的一个二分标号是一个双射f,且存在一个正整数k,使得f(u)≤k≤f(v),则顶点u和v属于树T的顶点集的二部分划分的不同部集.定义了全优美标号空间和k-二分全优美树,证明了一类二分全优美树,给出一些大型二分全优美树的构造方法.
【总页数】4页(P132-135)
【作者】姚明;黄建华;姚兵
【作者单位】兰州石化职业技术学院,甘肃兰州 730060;兰州石化职业技术学院,甘肃兰州 730060;西北师范大学数学与信息科学学院,甘肃兰州730070
【正文语种】中文
【中图分类】O157.5
【相关文献】
1.连路树的全优美性 [J], 张明军
2.关于一类蜘蛛树的全优美性 [J], 张明军
3.关于树的二分优美标号 [J], 姚明;姚兵;杨思华
4.一类蜘蛛树的(k,d)-优美标号 [J], 张明军
5.某些树的标号图及优美标号 [J], 李登信
因版权原因，仅展示原文概要，查看原文内容请购买。

两类并图的优美标号
张志尚;黄文强;东恺
【期刊名称】《东北师大学报：自然科学版》
【年(卷),期】2013()2
【摘要】讨论2n个优美二分图与一条通路并的优美性,得到如下结论:设二分图G=(X,Y,E)优美,优美标号为θ,边数为
q,a=max{k|0<k<q,k≠(v),v∈V(G)},b=min{k|0<k<q,k≠(v),v∈V(G)},h=min{q-a,b},pm为m长简单路.(1)当m=2n-1或m≥2n+h时,(2n)G∪pm是优美的.(2)若q为奇数,则图(q+2)G是优美的.
【总页数】5页(P30-34)
【关键词】优美标号;优美二分图;不交并;路;齿轮
【作者】张志尚;黄文强;东恺
【作者单位】吉林工程技术师范学院应用理学院;东北师范大学数学与统计学院;长春理工大学电子信息工程学院
【正文语种】中文
【中图分类】O157.6
【相关文献】
1.两类太阳图的奇优美标号 [J], 谢建民;刘海涛;毛耀忠
2.图的超边优美标号和奇优美标号 [J], 高振滨;孙广毅;邱威
3.两类圈相关图的奇优美标号 [J], 谢建民;姚兵;张锐
4.一类联图的优美标号与序列标号 [J], 刘春峰;任志考;王秀英
5.一类图的优美标号与序列标号 [J], 徐美进;刘春峰;高洋
因版权原因，仅展示原文概要，查看原文内容请购买。

图G_n×P_2的优美性
杨燕昌;王广选
【期刊名称】《数学研究与评论：英文版》
【年(卷),期】1992(12)1
【摘要】在文[l]中,我们证明了图C_4k×P_m的优美性,并且提出了一般地
C_n×P_m是优美图的猜想,在本文中我们证明了图C_n×P_2的优美性.定理图
C_n×P_2是优美图.我们将图G=C_n×P_2的2n个顶点分别记为u_i,u_i,i=l,2,…,n,其位置如图1所示.首先给出两种难以归属到一般情况的,n=3,n=5情况各顶点的优美值,见图2.至于n=4的情况,文[1]已经给出,这儿就不给出了.
【总页数】6页(P143-148)
【关键词】图CnXP2;优美图;优美值;优美标号
【作者】杨燕昌;王广选
【作者单位】北京工业大学;北京密云电机厂
【正文语种】中文
【中图分类】O157.5
【相关文献】
1.非连通图(P_2∨K_n)(r_1,r_2,…,r_(n+2))∪G_r的优美性 [J], 吴跃生;王广富;徐保根
2.关节r－p_n×p_2的K－优美性结论 [J], 卜长江;高振滨;张东波
3.积图p_m×p_n×p_2和双积图2p_m×p_n×p_2的k-优美性 [J], 曾朝英
4.关于P_2×P_n,F_(n,4)和C_(4,n,2)的k-优美性 [J], 赵立宽
5.非连通图2C_m∪C_n∪P_2的优美性 [J], 吴跃生;王广富;徐保根
因版权原因，仅展示原文概要，查看原文内容请购买。