The L(d, 1)-hole index of paths and cycles
Abstract
An L(j, k)-labeling of a graph G, where j ≥ k, is defined as a function f: V(G) → Z+ ∪ {0} such that if u and v are adjacent vertices in G, then |f(u) - f(v)| ≥ j, while if u and v are vertices such that d(u,v) = 2, then |f(u) - f(v)| ≥ k. The largest label used by / is the span of f, denoted span(f). The smallest span among all L(j, k)-labelings of G, denoted λj,k(G), is called the span of G. An L(j, k)-labeling of G that has a span of λj,k(G) is called a span labeling of G. We say that a span labeling f has ℓ holes if the set {i | f -1({i}) = θ where 1 ≤ i ≤ span(f) - 1} has cardinality ℓ. The hole index of G, denoted ρj,k(G), is defined as the minimum number of holes over all span L(j, k)-labelings of G. We determine the hole index of paths and cycles for the case when k = 1.
