Distance Consistent Labellings and the Local List Number

Abstract: We study the local list number of graphs introduced by Lennerstad and Eriksson. A labelling of a graph on n vertices is a bijection from vertex set to the set {1,…, n}. Given such a labelling c a vertex u is distance consistent if for all vertices v and w |c(u)-c(v)|=|c(u)-c(w)|+1 implies d(u,w)≤ d(u,v). A graph G is k-distance consistent if there is a labelling with k distance-consistent vertices. The local list number of a graph G is the largest k such that G is  k-distance consistent. We determine the local list number of cycles, complete bipartite graphs and some trees as well as prove bounds for some families of trees. We show that the local list number of even cycles is two, and of odd cycles is three. We also show that, if  k, l≥ 3 , the complete bipartite graph  Kk,l has local list number one, the star graph Sn=K1,n has local list number 3, and K2,k  has local list number 2. Finally, we show that for each n≥3 and each k such that 3≤k≤n there is a tree with local list number k.