有向圖的優(yōu)美性

斯琴巴特爾,馮偉

(內(nèi)蒙古民族大學(xué)數(shù)學(xué)學(xué)院,內(nèi)蒙古通遼 028043)

斯琴巴特爾,馮偉

(內(nèi)蒙古民族大學(xué)數(shù)學(xué)學(xué)院,內(nèi)蒙古通遼 028043)

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

有向圖;有向圈;優(yōu)美圖;優(yōu)美標(biāo)號(hào)

1 引言

圖論是數(shù)學(xué)的一個(gè)分支,特別是離散數(shù)學(xué)的一個(gè)重要分支,它在物理、化學(xué)、天文、地理、生物學(xué),尤其是在計(jì)算機(jī)科學(xué)中有著非常廣泛的應(yīng)用.圖的標(biāo)號(hào)問題是圖論中極有趣的一個(gè)研究課題,有著較好的研究價(jià)值和廣闊的應(yīng)用背景.

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

2 主要結(jié)果及例子

圖1的優(yōu)美標(biāo)號(hào)

圖2的優(yōu)美標(biāo)號(hào)

[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]馬克杰.優(yōu)美圖[M].北京:北京大學(xué)出版社,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.

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

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

2010 MSC:05C78