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

[摘要] An -coloring of a simple connected graphis an assignmentof nonnegative integers to the vertices ofsuch thatifandiffor all , wheredenotes the distance betweenandin . The span ofis the maximum color assigned by . The span of a graph , denoted by , is the minimum of span over all -colorings on . An -coloring ofwith spanis called a span coloring of . An -coloringis said to be irreducible if there exists no -coloring g such thatfor allandfor some . Ifis an -coloring with span , thenis a hole if there is nosuch that . The maximum number of holes over all irreducible span colorings ofis denoted by . A treewith maximum degreehaving spanis 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.

[学科分类] 应用数学