Optimal L(h,k)-Labeling of Regular Grids
The L(h, k)-labeling is an assignment of non negative integer labels to the nodes of a graph such that 'close' nodes have labels which differ by at least k, and 'very close' nodes have labels which differ by at least h. The span of an L(h,k)-labeling is the difference between...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2006-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Online Access: | http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/506 |
| _version_ | 1811294021436309504 |
|---|---|
| author | Tiziana Calamoneri |
| author_facet | Tiziana Calamoneri |
| author_sort | Tiziana Calamoneri |
| collection | DOAJ |
| description | The L(h, k)-labeling is an assignment of non negative integer labels to the nodes of a graph such that 'close' nodes have labels which differ by at least k, and 'very close' nodes have labels which differ by at least h. The span of an L(h,k)-labeling is the difference between the largest and the smallest assigned label. We study L(h, k)-labelings of cellular, squared and hexagonal grids, seeking those with minimum span for each value of k and h ≥ k. The L(h,k)-labeling problem has been intensively studied in some special cases, i.e. when k=0 (vertex coloring), h=k (vertex coloring the square of the graph) and h=2k (radio- or λ-coloring) but no results are known in the general case for regular grids. In this paper, we completely solve the L(h,k)-labeling problem on regular grids, finding exact values of the span for each value of h and k; only in a small interval we provide different upper and lower bounds. |
| first_indexed | 2024-04-13T05:11:07Z |
| format | Article |
| id | doaj.art-92ae4f260e8b44c39c27d1f0d363e337 |
| institution | Directory Open Access Journal |
| issn | 1462-7264 1365-8050 |
| language | English |
| last_indexed | 2024-04-13T05:11:07Z |
| publishDate | 2006-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-92ae4f260e8b44c39c27d1f0d363e3372022-12-22T03:01:02ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1462-72641365-80502006-01-0181Optimal L(h,k)-Labeling of Regular GridsTiziana CalamoneriThe L(h, k)-labeling is an assignment of non negative integer labels to the nodes of a graph such that 'close' nodes have labels which differ by at least k, and 'very close' nodes have labels which differ by at least h. The span of an L(h,k)-labeling is the difference between the largest and the smallest assigned label. We study L(h, k)-labelings of cellular, squared and hexagonal grids, seeking those with minimum span for each value of k and h ≥ k. The L(h,k)-labeling problem has been intensively studied in some special cases, i.e. when k=0 (vertex coloring), h=k (vertex coloring the square of the graph) and h=2k (radio- or λ-coloring) but no results are known in the general case for regular grids. In this paper, we completely solve the L(h,k)-labeling problem on regular grids, finding exact values of the span for each value of h and k; only in a small interval we provide different upper and lower bounds.http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/506 |
| spellingShingle | Tiziana Calamoneri Optimal L(h,k)-Labeling of Regular Grids Discrete Mathematics & Theoretical Computer Science |
| title | Optimal L(h,k)-Labeling of Regular Grids |
| title_full | Optimal L(h,k)-Labeling of Regular Grids |
| title_fullStr | Optimal L(h,k)-Labeling of Regular Grids |
| title_full_unstemmed | Optimal L(h,k)-Labeling of Regular Grids |
| title_short | Optimal L(h,k)-Labeling of Regular Grids |
| title_sort | optimal l h k labeling of regular grids |
| url | http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/506 |
| work_keys_str_mv | AT tizianacalamoneri optimallhklabelingofregulargrids |