有向圖的優美性

斯琴巴特爾,馮偉

(內蒙古民族大學數學學院,內蒙古通遼 028043)

斯琴巴特爾,馮偉

(內蒙古民族大學數學學院,內蒙古通遼 028043)

圖論是數學的一個分支,特別是離散數學的一個重要分支,它在物理、化學、天文、地理、生物學,尤其是在計算機科學中有著非常廣泛的應用.圖的標號問題是圖論中極有趣的一個研究課題,有著較好的研究價值和廣闊的應用背景.圖的一個頂點標號是頂點集合到非負整數集合的映射,而邊標號是邊集合到非負整數集合的映射,根據對映射的不同要求,產生了各種各樣的圖的標號問題,有向圖的優美標號是其中的一類. 用表示有n個頂點的有向圈,m表示m個無公共頂點的有向圈之并,本文研究了有向圖的優美性,利用搜索圖的標號的算法與數學證明相結合的方法,證實了有向圖為優美圖,其中n=2p,p為任意正整數.

有向圖;有向圈;優美圖;優美標號

1 引言

圖論是數學的一個分支,特別是離散數學的一個重要分支,它在物理、化學、天文、地理、生物學,尤其是在計算機科學中有著非常廣泛的應用.圖的標號問題是圖論中極有趣的一個研究課題,有著較好的研究價值和廣闊的應用背景.

是一個雙射,其中對任意的邊(u,v)∈E(D),有

2 主要結果及例子

圖1的優美標號

圖2的優美標號

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

[3]馬克杰.優美圖[M].北京:北京大學出版社,1991.

[5]Body J A,Murty U S R.Graph Theory with Applications[M].New York:Macmillan,London and Elsevier, 1976.

On the gracefulness of the digraph

Siqinbate,Feng Wei
(College of Mathematics,Inner Mongolian University for Nationalities,Tongliao 028043,China)

Graph theory is a branch of mathematics，especially an important branch of discrete mathematics，it has been applied in physics，chemistry，astronomy，geography，biology，especially in computer science has a very widely of applications.Graphs labeling problem is very interesting research subject in the graph theory,which has good value of research and wide prospect of application.Vertex labeling is a mapping that maps the vertex set into nonnegative integer set，while edge labeling is a mapping that maps edge set into nonnegative integer set.According to the different requirement for the mapping，varieties of graph labeling problem have been evolved，graceful labeling of digraph is one of the types.Letdenotes the directed cycle on n vertices,denotes the graph obtained from any m copies of.This paper discusses the gracefulness of the digraph.Using the algorithm for searching graph labeling combining with mathematical prove,we verify that the digraphis graceful if m=3 and n is even.

digraph,directed cycles,graceful graph,graceful labeling

O157.5

A

1008-5513(2013)02-0111-07

10.3969/j.issn.1008-5513.2013.02.001

2012-06-06.

國家自然科學基金(61262018).

斯琴巴特爾(1963-),教授,研究方向：組合數學.

2010 MSC:05C78