东南大学学报（英文版）
東南大學學報（英文版）
동남대학학보（영문판）
JOURNAL OF SOUTHEAST UNIVERSITY
2005年
1期
111-114
,共4页
L(d,1)-标号%边跨度%正三角形网格%正四边形网格%弦图%r-路
L(d,1)-標號%邊跨度%正三角形網格%正四邊形網格%絃圖%r-路
L(d,1)-표호%변과도%정삼각형망격%정사변형망격%현도%r-로
L(d,1)-labeling%edge span%triangular lattice%square lattice%choral graphs%r-path
对于给定图G顶点集上一个非负整数函数f,满足:若dG(u,v)＝1,f(u)-f(v)≥d;若 dG(u,v)＝2,f(u)-f(v)≥1.称f 为L(2,1)-标号.这是由频道分配问题抽象出来的数学模型.本文主要研究该标号问题的一个参数,即边跨度,记作βd(G)＝minf max{f(u)-f(v):u∈V(G)},即对于所有正常的L(d,1)-标号,使得相邻顶点标号之差的最大值达到最小.本文主要讨论了圈Cn、树T、 k-部完全图、正三角形网格、 正四边形网格以及弦图等图类的边跨度,并给出了确切的数值.
對于給定圖G頂點集上一箇非負整數函數f,滿足:若dG(u,v)＝1,f(u)-f(v)≥d;若 dG(u,v)＝2,f(u)-f(v)≥1.稱f 為L(2,1)-標號.這是由頻道分配問題抽象齣來的數學模型.本文主要研究該標號問題的一箇參數,即邊跨度,記作βd(G)＝minf max{f(u)-f(v):u∈V(G)},即對于所有正常的L(d,1)-標號,使得相鄰頂點標號之差的最大值達到最小.本文主要討論瞭圈Cn、樹T、 k-部完全圖、正三角形網格、 正四邊形網格以及絃圖等圖類的邊跨度,併給齣瞭確切的數值.
대우급정도G정점집상일개비부정수함수f,만족:약dG(u,v)＝1,f(u)-f(v)≥d;약 dG(u,v)＝2,f(u)-f(v)≥1.칭f 위L(2,1)-표호.저시유빈도분배문제추상출래적수학모형.본문주요연구해표호문제적일개삼수,즉변과도,기작βd(G)＝minf max{f(u)-f(v):u∈V(G)},즉대우소유정상적L(d,1)-표호,사득상린정점표호지차적최대치체도최소.본문주요토론료권Cn、수T、 k-부완전도、정삼각형망격、 정사변형망격이급현도등도류적변과도,병급출료학절적수치.
Given a graph G and a positive integer d,an L(d,1)-labeling of G is a function f that assigns to each vertex of G a non-negative integer such that f(u)-f(v)≥d if dG(u,v)＝1;f(u)-f(v)≥1 if dG(u,v)＝2.The L(d,1)-labeling number of G,λd(G) is the minimum range span of labels over all such labelings,which is motivated by the channel assignment problem.We consider the question of finding the minimum edge span βd(G) of this labeling.Several classes of graphs such as cycles,trees,complete k-partite graphs,chordal graphs including triangular lattice and square lattice which are important to a telecommunication problem are studied,and exact values are given.
