Reconfiguration of List L(2,1)-Labelings in a Graph (コンピュテーション) Reconfiguration of List L(2,1)-Labelings in a Graph

Search this Article

Author(s)

Abstract

あらまし非負整数κ≧0に対し,グラフGの各点νには,ラベルの集合0(ν)⊆{0,1,...,κ}が与えられているとする.このとき,σのリストL(2,1)ラベリングとは,σの各点勿に0@)に含まれるラベルを1つ割り当てることをいう.ただし,隣接する任意の2点には少なくとも2離れたラベルを割り当て,距離2にある任意の2点には少なくとも1離れたラベルを割り当てなければならない.本論文では,グラフGのリストL(2,1)ラベリングが2つ与えられたとき,一方のラベル割当から他方のラベル割当へ段階的に遷移させたい.ただし,1回に変更できるのは1点のラベル割当のみであり,こうして得られるラベル割当もやはりGのリストL(2,1)ラベリングでなければならない.本論文では,κ≧6のとき,この問題は平面二部グラフに対してPSPACE完全であることを証明する.一方で,κ≦4のときには,この問題が任意のグラフに対して線形時間で解けることを示す.さらに,グラフを木に限定したとき,任音の2つのリストL(2.1、ラベリングが互いに遷移できるための十分条件を与える.

Abstract For an integer κ≧O, suppose that each vertex v of a graph G has a set C(ν)⊆{O,1,...,κ} of labels, called a list of v. A list L(2,1)-labeling of G is an assignment of a label in C(v) to each vertex v of G such that every two adjacent vertices receive labels which differ by at least 2 and every two vertices of distance two receive labels which differ by at least 1. In this paper, we study the problem of reconfiguring one list L(2,1)-labeling of a graph into another list L(2,1)-labeling of the same graph by changing only one label assignment at a time, while at all times maintaining a list L(2,1)-labeling. First we show that this decision problem is PSPACE-complete, even for bipartite planar graphs and κ≧6. In contrast, we then show that the problem can be solved in linear time for general graphs if κ≦4. We finally consider the problem restricted to trees, and give a sufficient condition for which any two list L(2,1)-labelings of a tree can be transformed into each other.

Journal

  • IEICE technical report. Theoretical foundations of Computing

    IEICE technical report. Theoretical foundations of Computing 112(340), 33-40, 2012-12-10

    The Institute of Electronics, Information and Communication Engineers

Codes

  • NII Article ID (NAID)
    110009670153
  • NII NACSIS-CAT ID (NCID)
    AN10013152
  • Text Lang
    ENG
  • ISSN
    0913-5685
  • NDL Article ID
    024197692
  • NDL Call No.
    Z16-940
  • Data Source
    NDL  NII-ELS 
Page Top