摘要
图的顶点标号是顶点集合到非负整数集合的映射,而边标号是边集合到非负整数集合的映射,根据对映射的不同要求,产生了各种各样的图的标号问题,有向图的优美标号是其中的一类.图的标号问题是图论中极为有趣的一个研究课题,有着较好的研究价值和广阔的应用背景.用C_m(向量)表示有m个顶点的有向圈,n·C_m(向量)表示共用同一个顶点的n个有向圈C_m(向量)之并.以往研究了n·C_3(向量)及n·C_3(向量)的无交并的优美性,并得出结果:n·C_3(向量)是优美图;两个无交有向图n·C_3(向量)之并为优美图;四个两两无交有向图n·C_3(向量)之并为优美图;六个两两无交有向图n·C_3(向量)之并为优美图.本文继续给出结果:当n为偶数时,三个两两无交有向图n·C_3(向量)之并为优美图,并猜想:m个两两无交有向图n·C_3(向量)之并为优美图的充分且必要条件为mn≡0(mod 2).
Vertex labeling of graphs maps the vertex set into a nonnegative integer set,while edge labeling of graphs maps the edge set into a nonnegative integer set. Graceful labeling of digraph is a type of graph labeling with a wide prospect of application. Let Cm^→denote the directed cycle on m vertices,n·Cm^→denotes the graph obtained from any n copies of Cm^→which have just one common vertex. Past, studies on the gracefulness of graphs n·C3^→and gracefulness of union of mutually non-intersecting digraphs n·C3^→,demonstrated the following were graceful： digraphs n·C3^→; union of two mutually non-intersecting digraphs n·C3^→; union of four mutually non-intersecting digraphs n·C3^→; and union of six mutually non-intersecting digraphs n·C3^→. We now demonstrate that the union of three mutually non-intersecting digraphs n·C3^→is graceful if n is even,and conjecture that the union of m numbers mutually non-intersecting digraphs n·C3^→is graceful if and only if mn ≡ 0（mod 2）.
作者
斯琴巴特尔
李春龙
Siqinbate, LI Chun-long(College of Mathematics, Inner Mongolia University for Nationalities ,Tongliao 028043, Chin)
出处
《内蒙古民族大学学报（自然科学版）》
2017年第2期93-97,共5页
Journal of Inner Mongolia Minzu University：Natural Sciences
基金
国家自然科学基金资助项目(NO6126018)
关键词
有向图
有向圈
优美标号
优美图
Digraph
Directed Cycles
Graceful Labeling
Graceful Graph
