任意 n 个完备二分图的并图的优美性
- 格式:pdf
- 大小:398.84 KB
- 文档页数:4
浅谈稳定完备婚姻的算法及推广话说在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], 吴跃生;王广富;徐保根
因版权原因,仅展示原文概要,查看原文内容请购买。