图的L(p,q)-标号问题  

On L(p,q)-labeling of graphs

作　　者：朱海洋[1] 

机构地区：[1]浙江师范大学数理学院,浙江金华321004

出　　处：《宝鸡文理学院学报（自然科学版）》2006年第1期23-27,共5页Journal of Baoji University of Arts and Sciences(Natural Science Edition)

基　　金：浙江省自然科学基金资助(102055)

摘　　要：令G为图,p,q为2个正整数,p≥q。G的一个L(p,q)-标号是映射f:V(G)→{0,1,2,…},使得对任意x,y∈V(G),若dG(x,y)=1则|f(x)-f(y)|≥p;若dG(x,y)=2则|f(x)-f(y)|≥q。G的一个m-L(p,q)-标号是标号f:V(G)→{0,1,2,…},使得对任意x∈V(G),有f(x)≤m。并称λp,q(G)=min{m|存在G的一个m-L(p,q)-标号}为图G的L(p,q)-数。本文给出k-退化图、G1和G2的联图G1∨G2及G1和G2的M-matched sum图G1M+G2的L(p,q)-数不同上界。最后给出仙人掌图,唯一圈图L(p,1)-数λp,1(G)的可达界。Given a graph g and positive integers p≥q, an L（p,q）-labeling of g is a function f： V （G）→{0,1,2,...} ,such that, for any two vertices x,y∈V（G）, ｜f（x）-f（y）｜≥p if dG（x,y）=1; and ｜f{x}-f（y）｜≥q if dG（x,y）=2. An m-L（p,q）-labeling is an L（p,q）-labeling so that no label used is greater than m. The L（ p ,q ）-number of g, denoted by λp,q（G）, is the smallest number m such that g has an m-L（p,q）-labeling, different upper bound of some families of graphs incluing k-degenerated graph,joins G1 ∨ G2 of graphs G1 and G2, M-matched sum G1M^＋ G2 of G1 and G2 are presented. In particular, we show that the lower and the upper bounds of λp,1 （G）, for cactus and unicycle are both attainable.

关 键 词：L(p q)-标号 M-matched sum图 仙人掌图 L(p q)-数 

分 类 号：O157.5[理学—数学] O156.1[理学—基础数学]