图的(2,1)-点面标号

The (2,1)-total labelling of the product of two kinds of graphs

图G的一个k-(2,1)-点面标号是一个映射c:V(G)∪F(G)→{0,1,…,k},使得相邻的顶点取不同的值,相邻的面取得不同的值,相关联的点面取值至少相差2.G的(2,1)-全标号数λvf2(G)定义为G所有的k-(2,1)-点面标号中最小的k值.给出了树、圈、欧拉二部图、K4、外平面图等简单图类的(2,1)-点面标号数的上界,而且完全刻画了至多含有一个闭内面的外平面图的(2,1)-点面标号数.

A k-（2,1 ） -coupled labelling of a plane graph G was defined as a mapping from V（G） ∪F（G） to {0,1 ,… ,k} such that adjacent vertices or adjacent faces received different numbers, and numbers of the ver- tex and the face incidentally received differed by at least 2. The （2,1） -coupled labelling number λof 2（G） of G was defined as the smallest integer k such that G had a k- （ 2,1 ） -coupled labelling. A tight upper bounds of （ 2,1 ） -total labelling number were given for trees, cycles, K4, Eulerian bipartite graphs, outerplanar graphs, etc. In addition, a complete characterization of （ 2,1 } -coupled labelling numbers for outerplanar graphs with at most one closed inner face was presented.