一个路与一个完全图的直积的L(2,1)-标号

L(2,1)-Labeling of the Direct Product of a Path and a Complete Graph

摘要: 为了得到一个路P_m与一个完全图K_n的直积P_m×K_n的L(2,1)-标号数,通过归纳猜想,分类讨论,证明了m=3或4时,P_m×K₃的L(2,1)-标号数为6, m≥5时,P_m×K₃的L(2,1)-标号数为7, m≥5且n≥3时,P_m×K_n的L(2,1)-标号数的上界是3n-2

Abstract: In order to obtain the L(2,1)-labeling of the direct product P_m×K_n of a pathP_m and a complete graph K_n, by means of induction, conjecture and classified discussion, the L(2,1)-labeling number of P_m×K₃ is determined as 6 if m=3 or 4, and the L(2,1)-labeling number of P_m×K_n is determined as 7 if m≥5.The upper bound of the L(2,1)-labeling number of P_m×K_n is shown at most m≥n-2 if m≥n-2 and n≥3