讲座题目： Star Matching and Distance Two Labelling

主讲人: Dr.林文松

时 间: 2007.11.7, 2:00-3:00 pm

地 点: C305

摘 要: In this talk, we introduce a new graph parameter, called t-star-matching number of a graph. We design a polynomial time algorithm to compute the t-star-matching number for any graph. We then relate the 4-star-matching number of a graph to the so called L(2,1)-labeling number of a graph. This leads to a polynomial time algorithm to compute the L(2,1)-labeling numbers of certain classes of graph.