有向图的优美性

包晶晶[1,2],斯琴其木格[3],杨元生[1,4],吉日木图[1,2]

(1.内蒙古民族大学离散数学研究所,内蒙古通辽028043; 2.内蒙古民族大学数学学院,内蒙古通辽028043;

3.赤峰学院计算机学院,内蒙古赤峰024000;

4.大连理工大学计算机科学与技术学院,辽宁大连116024)

包晶晶[1,2],斯琴其木格[3],杨元生[1,4],吉日木图[1,2]

(1.内蒙古民族大学离散数学研究所,内蒙古通辽028043; 2.内蒙古民族大学数学学院,内蒙古通辽028043;

3.赤峰学院计算机学院,内蒙古赤峰024000;

4.大连理工大学计算机科学与技术学院,辽宁大连116024)

摘要：研究了有向图的优美性,利用搜索图的标号的算法与数学证明相结合的方法,证明了有向图−→为优美图,其中n为任意正整数.

关键词：有向图;有向圈;优美图;优美标号

1 引言

设G=(V,E)为有向图,如果存在单射θ:V(G)−→{0,1,2,···,|E|},使得诱导映射θ′:E(G)−→{1,2,···,|E|}是双射,其中对任意的边uv∈E(G),有

则θ称为有向图G=(V,E)的优美标号,θ′称为有向图G=(V,E)的边优美标号.用表示有n(≥3)个顶点的有向圈,表示m个无公共顶点的有向圈之并.目前,关于有向圈相关图的优美性的研究结果有m(见文献[1-2])和m−(见文献[3-4])为优美图.关于有向图的优美性的结论有见文献[5])和(见文献6])是优美图.文献[7]给出:有向图优美的必要条件为mn≡0(mod 2),并提出猜想:当mn≡0(mod 2)时,有向图为优美图.本文给出了有向图是优美图,其中n为任意正整数.

2 主要结果

定理2.1当n≡0(mod 2)时,有向图为优美图.

证明设有向图的四个有向圈为顶点依次为:

情形1当n≡0(mod 4)时,的顶点标号定义如下:

情形2当n≡2(mod 4)时,的顶点标号定义如下:

其次证明,情形1中顶点标号所诱导的边标号θ′是E()到{1,2,···,4n}的一一映射.

由上可知,取值为偶数的边标号有:

其中

由以上的讨论可知,A,B,C,D,E,F,G,H中的数彼此不相同,从而得知取值为偶数的边标号集合为{2,4,···,4n}.同理,取值为奇数的边标号集合为{1,3,···,4n−1}.所以θ′是到{1,2,···,4n}的一一映射.故上述θ为优美标号.

类似情形1的方法,在情形2中定义θ所确定的顶点标号集为{0,1,2,···,4n}−{n},θ所诱导的θ′是E()到{1,2,···,4n}的一一映射.故θ为优美标号.

定理2.2当n≡1(mod 2)时,有向图为优美图.

证明设有向图4−→Cn的四个有向圈为{)|i=1,2,3,4},顶点依次为

类似于定理2.1的证明方法,在情形(1),情形(2)中定义的θ均为优美标号.

参考文献

[1] Jirimutu,Xu Xirong,Feng Wei,et al.Proof of a conjecture on the gracefulness of a digraph[J].Utilitas Mathematica,2010,81:255-264.

[3] Zhao L,Jirimutu,Xu X,et al.On the gracefulness of the digraphs n−for m odd.[J].J Prime Res. Math.,2008,4:118-126.

[4] Hegde S M,Shivarajkumar.Two conjectures on graceful digraphs[J].Graphs and Combinatorics,2013,29:933-954.

[7] 马克杰.优美图[M].北京:北京大学出版社,1991.

2010 MSC:05C69

中图分类号：O157.5

文献标识码：A

文章编号：1008-5513(2014)05-0543-08

DOI：10.3969/j.issn.1008-5513.2014.05.016

收稿日期：2014-04-03.

基金项目：国家自然科学基金(61262018).

作者简介：包晶晶(1989-),硕士生,研究方向：图论及其应用.

On the Gracefulness of the Digraph

Bao Jingjing[1,2],Siqinqimuge[4],Yang Yuansheng[1,3],Jirimutu[1,2]
(1.Institute of Discrete Mathematics,Inner Mongolia University for Nationalities,Tongliao028043,China; 2.College of Mathematics,Inner Mongolia University for Nationalities,Tongliao028043,China; 3.College of Computer,Chifeng University,Chifeng024000,China; 4.College of Computer Science and Technology,Dalian University of Technology,Dalian116024,China)

Abstract:This paper researches the gracefulness of digraph m−→Cn.By utilizing algorithm of searching for graph labeling and combining with mathematical proof,this paper proves that digraph 4−→Cnis graceful for any positive integer n.

Key words:digraph,directed cycles,graceful graph,graceful labeling