講者：林逸軒 博士 (慈濟大學附屬高級中學)
時間：113年5月3日(星期五)下午13：30-15：00
地點：民生校區五育樓4樓401教室
摘要
Let G be a graph, and let s_d: d_1,d_2,…,d_k, s_r^*: r_1,r_2,…,r_k be two sequences of positive integers. A set S⊆V(G) is an (s_d;s_r^* )-resolving set for G if N_S^(d_k )≠0 for any vertex v in V(G)-S (N_S^(d_k ) (v)={u∈S:d(u,v)≤d_k }), and for any two distinct vertices u,v in V(G)-S, we have |N_S^(d_i ) (u)∆N_S^(d_i ) (v)|≥r_i for some i,1≤i≤k, (N_S^(d_i ) (v)={u∈S:d(u,v)≤d_i }) where N_S^(d_i ) (u)∆N_S^(d_i ) (v) denotes the symmetric difference of N_S^(d_i ) (u)and N_S^(d_i ) (v). An (s_d;s_r^* )-basis for G is an (s_d;s_r^* )-resolving set for G with the minimum cardinality, and the (s_d;s_r^* )-dimension of G refers to its cardinality. We call an (s_d;s_r^* )-resolving set for G a [1,k]-resolving set for G, and call an (s_d;s_r^* )-basis for G a [1,k]-basis for G, when s_d and s_r^* are both the sequence 1,2,…,k, for simplicity. The size of a [1,k]-basis for G is called the [1,k]-dimension for G and is denoted by dim_[1,k] (G). We study the [1,2]-dimension of graphs in this paper. We prove that the [1,2]-dimension problem is an NP-complete problem, and determine the [1,2]-dimension of some classes of graphs, such as paths, cycles, and full k-ary trees.