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

An -coloring of a simple connected graph is an assignment of nonnegative integers to the vertices of such that if and if for all , where denotes the distance between and in . The span of is the maximum color assigned by . The span of a graph , denoted by , is the minimum of span over all -colorings on . An -coloring of with span is called a span coloring of . An -coloring is said to be irreducible if there exists no -coloring g such that for all and for some . If is an -coloring with span , then is a hole if there is no such that . The maximum number of holes over all irreducible span colorings of is denoted by . A tree with maximum degree having span 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.