有向图n·■_9的优美性

Gracefulness of digraph n·(C|-)_9

设Cm表示具有m个顶点的有向圈,n·Cm表示由仅具有一个公共顶点的n有向圈Cm组成的有向图.1994年杜之亭,孙惠泉在证明了n·C2p(n≡0(mod2))是优美图的基础上提出猜想"n·C2p+1(n≡0(mod2))是优美的",之后,很多学者在这方面做了大量的工作,并分别证明了猜想对于p=1,2,3是成立的.本文证明了猜想对于p=4(即有向图n·C9(n≡0(mod2))也是成立的,并且给出了三种不同的优美标号.猜想对于任意正整数p是否成立,仍然是个公开问题.

Let the digraph Cm be a directed circuit with m vertices. Let n·Cm denote a digraph with exactly a common vertex on n copies of the digraph Cm . In 1994, Du Z T and Sun H Q proved the gracefulness of the digraph n·C2p (n≡0(mod2)). Based on it, they conjectured that the digraph n·C2p+1(n≡0(mod2)) is a graceful digraph. Since then, it has been proved that the conjecture is true for p = 1,2,3 by different authors. In this paper, we prove that the conjecture is true for p = 4, and three different graceful labelings of the digraph n·C9(n≡0(mod 2)) are given. The conjecture remains open for arbitrarily large positive number p.