Distance Two Surjective Labelling of Paths and Interval Graphs

[摘要] Graph labelling problem has been broadly studied for a long period for its applications, especially in frequency assignment in (mobile) communication system, - ray crystallography, circuit design, etc. Nowadays, surjective - labelling is a well-studied problem. Motivated from the - labelling problem and the importance of surjective - labelling problem, we consider surjective - labelling ( - labelling) problems for paths and interval graphs. For any graph , an - labelling is a mapping so that, for every pair of nodes and , if , then ; and if , then , and every label is used exactly once, where represents the distance between the nodes and , and is the number of nodes of graph . In the present article, it is proved that any path can be surjectively - labelled if , and it is also proved that any interval graph having nodes and degree can be surjectively - labelled if . Also, we have designed two efficient algorithms for surjective - labelling of paths and interval graphs. The results regarding both paths and interval graphs are the first result for surjective - labelling.

[学科分类] 安全、风险、质量和可靠性