TY - JOUR

T1 - On L(2, 1)-labeling of generalized Petersen graphs

AU - Huang, Yuan Zhen

AU - Chiang, Chun Ying

AU - Huang, Liang Hao

AU - Yeh, Hong Gwa

N1 - Funding Information:
L.-H. Huang was partially supported by National Science Council under grant NSC99-2811-M-008-059. H.-G. Yeh was partially supported by National Science Council under grant NSC97-2628-M-008-018-MY3.

PY - 2012/10

Y1 - 2012/10

N2 - A variation of the classical channel assignment problem is to assign a radio channel which is a nonnegative integer to each radio transmitter so that "close" transmitters must receive different channels and "very close" transmitters must receive channels that are at least two channels apart. The goal is to minimize the span of a feasible assignment. This channel assignment problem can be modeled with distance-dependent graph labelings. A k-L(2, 1)-labeling of a graph G is a mapping f from the vertex set of G to the set {0, 1, 2, ⋯ , k} such that |f (x) - f (y)| ≤ 2 if d(x, y) = 1 and f (x) = f (y) if d(x, y) = 2, where d(x, y) is the distance between vertices x and y in G. The minimum k for which G admits an k-L(2, 1)-labeling, denoted by λ(G), is called the ?-number of G. Very little is known about ?-numbers of 3-regular graphs. In this paper we focus on an important subclass of 3-regular graphs called generalized Petersen graphs. For an integer n ≥ 3, a graph G is called a generalized Petersen graph of order n if and only if G is a 3-regular graph consisting of two disjoint cycles (called inner and outer cycles) of length n, where each vertex of the outer (resp. inner) cycle is adjacent to exactly one vertex of the inner (resp. outer) cycle. In 2002, Georges and Mauro conjectured that (G) ≤ 7 for all generalized Petersen graphs G of order n ≥ 7. Later, Adams, Cass and Troxell proved that Georges and Mauro's conjecture is true for orders 7 and 8. In this paper it is shown that Georges and Mauro's conjecture is true for generalized Petersen graphs of orders 9, 10, 11 and 12.

AB - A variation of the classical channel assignment problem is to assign a radio channel which is a nonnegative integer to each radio transmitter so that "close" transmitters must receive different channels and "very close" transmitters must receive channels that are at least two channels apart. The goal is to minimize the span of a feasible assignment. This channel assignment problem can be modeled with distance-dependent graph labelings. A k-L(2, 1)-labeling of a graph G is a mapping f from the vertex set of G to the set {0, 1, 2, ⋯ , k} such that |f (x) - f (y)| ≤ 2 if d(x, y) = 1 and f (x) = f (y) if d(x, y) = 2, where d(x, y) is the distance between vertices x and y in G. The minimum k for which G admits an k-L(2, 1)-labeling, denoted by λ(G), is called the ?-number of G. Very little is known about ?-numbers of 3-regular graphs. In this paper we focus on an important subclass of 3-regular graphs called generalized Petersen graphs. For an integer n ≥ 3, a graph G is called a generalized Petersen graph of order n if and only if G is a 3-regular graph consisting of two disjoint cycles (called inner and outer cycles) of length n, where each vertex of the outer (resp. inner) cycle is adjacent to exactly one vertex of the inner (resp. outer) cycle. In 2002, Georges and Mauro conjectured that (G) ≤ 7 for all generalized Petersen graphs G of order n ≥ 7. Later, Adams, Cass and Troxell proved that Georges and Mauro's conjecture is true for orders 7 and 8. In this paper it is shown that Georges and Mauro's conjecture is true for generalized Petersen graphs of orders 9, 10, 11 and 12.

KW - λ-regular graph

KW - ?-number

KW - Channel assignment

KW - Frequency allocation

KW - Generalized Petersen graph

KW - Interchannel interference

KW - L(2, 1)-labeling

KW - L(2, 1)-labeling number

UR - http://www.scopus.com/inward/record.url?scp=84867097428&partnerID=8YFLogxK

U2 - 10.1007/s10878-011-9380-8

DO - 10.1007/s10878-011-9380-8

M3 - 期刊論文

AN - SCOPUS:84867097428

SN - 1382-6905

VL - 24

SP - 266

EP - 279

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 3

ER -