Please use this identifier to cite or link to this item:

`https://idr.nitk.ac.in/jspui/handle/123456789/11617`

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

Authors: | Kola, S.R. Gudla, B. Niranjan, P.K. |

Issue Date: | 2018 |

Citation: | Journal of Applied Mathematics, 2018, Vol.2018, , pp.- |

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∈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∈V(G) and g(v)<f(v) for some v∈V(G). If f is an L(2,1)-coloring with span k, then h∈0,1,2,.,k is a hole if there is no v∈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. |

URI: | http://idr.nitk.ac.in/jspui/handle/123456789/11617 |

Appears in Collections: | 1. Journal Articles |

Files in This Item:

There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.