摘要
设G是简单无向图,|E(G)|=e. G称为是优美图,如果存在E(G)到{0,1,…,e}的一个单射f使得{|f((?))-f((?))| |(u,o)∈E(G)}={1,2,…,e}.A. Kotzig曾提出猜想“对于任意正整数j,k,图Q(j,4k)和Q(2j,4k+2)都是优美的”.本文证明,这一猜想对于Q(4,4k)和Q(4,4k+2)正确.作者还进一步证明了c(Q(2,4k+2),0(1,8k+4))的优美性.
Let G be an undirected simple graph and |E(G)|=e, G is called graceful if there exists a bijec-
tion f from V(G) onto{0,1,……,e} so that{|f(u) -f(υ)| | (u,υ)∈ E(G)}={1,2,……, e}.
A. Kotzig had posed the conjuncture that Q(j,4k) and Q(2j,4k+2) are graceful graph. In this paper we proved that the conjuncture is true for Q(4,4k) and Q(4,4k+2). Furthermore we proved that C(Q(2,4k+2), G(l,8k+4)) is graceful.
出处
《烟台大学学报（自然科学与工程版）》
CAS
1989年第2期25-31,共7页
Journal of Yantai University(Natural Science and Engineering Edition)
关键词
交错图
优美图
规格点
Alternating graph. Graceful graph
