Infinitely Many Trees with Maximum Number of Holes Zero, One, and Two

Abstract

An L(2,1)-coloring of a simple connected graph G is an assignment f of nonnegative integers to the vertices of G such that fu-fv2 if d(u,v)=1 and fu-fv1 if d(u,v)=2 for all u,v&Element;V(G), where d(u,v) denotes the distance between u and v in G. The span of f is the maximum color assigned by f. The span of a graph G, denoted by (G), is the minimum of span over all L(2,1)-colorings on G. An L(2,1)-coloring of G with span (G) is called a span coloring of G. An L(2,1)-coloring f is said to be irreducible if there exists no L(2,1)-coloring g such that g(u)f(u) for all u&Element;V(G) and g(v)<f(v) for some v&Element;V(G). If f is an L(2,1)-coloring with span k, then h&Element;0,1,2,.,k is a hole if there is no v&Element;V(G) such that f(v)=h. The maximum number of holes over all irreducible span colorings of G is denoted by H(G). A tree T with maximum degree ? having span ?+1 is referred to as Type-I tree; otherwise it is Type-II. In this paper, we give a method to construct infinitely many trees with at least one hole from a one-hole tree and infinitely many two-hole trees from a two-hole tree. Also, using the method, we construct infinitely many Type-II trees with maximum number of holes one and two. Further, we give a sufficient condition for a Type-II tree with maximum number of holes zero. 2018 Srinivasa Rao Kola et al.