摘要
图论是数学的一个分支,特别是离散数学的一个重要分支,它在物理、化学、天文、地理、生物学,尤其是在计算机科学中有着非常广泛的应用.图的标号问题是图论中极有趣的一个研究课题,有着较好的研究价值和广阔的应用背景.图的一个顶点标号是顶点集合到非负整数集合的映射,而边标号是边集合到非负整数集合的映射,根据对映射的不同要求,产生了各种各样的图的标号问题,有向图的优美标号是其中的一类.用■n表示有n个顶点的有向圈,m■n表示m个无公共顶点的有向圈C n之并,本文研究了有向图m■n的优美性,利用搜索图的标号的算法与数学证明相结合的方法,证实了有向图3■n为优美图,其中n=2p,p为任意正整数.
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 the- ory, 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. Let Cn denotes the directed cycle on n vertices, rnCdenotes the graph obtained from any m copies of Cn. This paper discusses the gracefulness of the digraph mC. Using the algorithm for searching graph labeling combining with mathematical prove, we verify that the digraph mCn is graceful if m = 3 and n is even.
出处
《纯粹数学与应用数学》
CSCD
2013年第2期111-117,共7页
Pure and Applied Mathematics
基金
国家自然科学基金(61262018)
关键词
有向图
有向圈
优美图
优美标号
digraph, directed cycles, graceful graph, graceful labeling
