## 【應數系演講】110-05-28 圖形的距離2標號問題 (改線上進行)

In the channel assignment problem, we need to assign frequency bands to transmitters, if two transmitters are too close, interference will occur if they attempt to transmit on close frequencies. In order to avoid this situation, the separation of the channels assigned to them must sufficient. Moreover, if two transmitters are close but not too close, the channel assigned must be different. This problem was known under the L(p,q)-labeling problem of a graph G, where an L(p,q)-labeling of G is an integer assignment f to the vertices of G such that for all u,v in V(G),d_G (u,v)=1 implies |f(u)-f(v)|≥p, and d_G (u,v)=2 implies |f(u)-f(v)|≥q. A k-L(p,q)-labeling is an L(p,q)-labeling such that no label is greater than k. The L(p,q)-labeling number of G, denoted by λ_(p,q) (G), is the smallest number k such that G has a k-L(p,q)-labeling. We study the L(p,q)-labeling numbers of subdivision of graphs in this paper. We prove that λ_(p,q)(G_((3)))=p+(Δ-1)q when p≥2q and Δ>2⌈(p/q)⌉. Based on this, we deduce that λ_(p,q)(G_((h)))=p+(Δ-1)q when p≥2q and Δ>3⌈(p/q)⌉, where h is a function from E(G) to ℕ so that h(e)≥3 for all e∈E(G). We also give some results on the n-fold L(2; 1)-labeling number of Cartesian product of paths and cycles.

※※※ 歡  迎  參  加 ※※※