摘要
该文定义:一个简单图G=（V,E）是k-优美的（k≥1为整数）,如果存在单射f:V（G）→{0,1,2,…,|E|+k-1}使得对所有的边uv∈E（G）,由f＊（VV）一丫（V）-/（V门导出的映射 f＊:E（G）→{k,k+1,…,|E|+k-1}是双射。若G是简单图,且在G的所有相邻的两个顶点之间都加入一个顶点,则所得到的图称为G的细分图。该文还证明了积图Pn×C2m、P2n×C2m+1、P2n×Cm的细分图是k-优美图。
Let k be a positive integer. The simple graph G = ( V, E) is called k-graceful if there exists an injectionf:V(G)→{0, 1, 2,…,OEO+k-1}, so that the following mapping is bijection:f*:E(G)-{k, k+1,…,OEO+k-1}, f* (uv) =|f(u)-f(v)|(u,v∈V(G),uv∈E(G) ).Let G be a simple graph, if one vertex is put between every two adjacent vertexes of G, then the produced graph is called a subdivision graph of G. In this paper, we verify the k-gracefulness on the subdivision graph of the product graphs Pn and C2m, P2n and C2m+1,P2, and Cm , where Ps denotes a chain with s vertices and C1 denotes a simple circle with t vertices.
基金
海南省高校科研项目
