跳到主要內容區

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

國立東華大學應用數學系

專    題    演    講

主講人:江適昂 博士生(國立東華大學應用數學系博士班 )

講 題:圖形的距離2標號問題

時 間:110 年 05月 28日 (星期五) 15:10-17:00

地 點:meet.google.com/kou-mctd-cxz (提前10分鐘,請將名稱顯示學號姓名)

摘  要

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.

POST




 

※※※ 歡  迎  參  加 ※※※

 

 
瀏覽數: