Infinitely Many Trees with Maximum Number of Holes Zero, One, and Two
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-fv⩾2 if d(u,v)=1 and fu-fv⩾1 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...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2018-01-01
|
| Series: | Journal of Applied Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2018/8186345 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832555474225987584 |
|---|---|
| author | Srinivasa Rao Kola Balakrishna Gudla P. K. Niranjan |
| author_facet | Srinivasa Rao Kola Balakrishna Gudla P. K. Niranjan |
| author_sort | Srinivasa Rao Kola |
| collection | DOAJ |
| description | 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-fv⩾2 if d(u,v)=1 and fu-fv⩾1 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. |
| format | Article |
| id | doaj-art-794cbfc8e04543728b0f292d16950aa3 |
| institution | Kabale University |
| issn | 1110-757X 1687-0042 |
| language | English |
| publishDate | 2018-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Applied Mathematics |
| spelling | doaj-art-794cbfc8e04543728b0f292d16950aa32025-02-03T05:48:03ZengWileyJournal of Applied Mathematics1110-757X1687-00422018-01-01201810.1155/2018/81863458186345Infinitely Many Trees with Maximum Number of Holes Zero, One, and TwoSrinivasa Rao Kola0Balakrishna Gudla1P. K. Niranjan2Department of Mathematical and Computational Sciences, National Institute of Technology Karnataka, Surathkal, IndiaDepartment of Mathematical and Computational Sciences, National Institute of Technology Karnataka, Surathkal, IndiaDepartment of Mathematical and Computational Sciences, National Institute of Technology Karnataka, Surathkal, IndiaAn 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-fv⩾2 if d(u,v)=1 and fu-fv⩾1 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.http://dx.doi.org/10.1155/2018/8186345 |
| spellingShingle | Srinivasa Rao Kola Balakrishna Gudla P. K. Niranjan Infinitely Many Trees with Maximum Number of Holes Zero, One, and Two Journal of Applied Mathematics |
| title | Infinitely Many Trees with Maximum Number of Holes Zero, One, and Two |
| title_full | Infinitely Many Trees with Maximum Number of Holes Zero, One, and Two |
| title_fullStr | Infinitely Many Trees with Maximum Number of Holes Zero, One, and Two |
| title_full_unstemmed | Infinitely Many Trees with Maximum Number of Holes Zero, One, and Two |
| title_short | Infinitely Many Trees with Maximum Number of Holes Zero, One, and Two |
| title_sort | infinitely many trees with maximum number of holes zero one and two |
| url | http://dx.doi.org/10.1155/2018/8186345 |
| work_keys_str_mv | AT srinivasaraokola infinitelymanytreeswithmaximumnumberofholeszerooneandtwo AT balakrishnagudla infinitelymanytreeswithmaximumnumberofholeszerooneandtwo AT pkniranjan infinitelymanytreeswithmaximumnumberofholeszerooneandtwo |