Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Optimal L(h,k)-Label ...
Article

Optimal L(h,k)-Labeling of Regular Grids

Tiziana Calamoneri ORCID (1)
(1) Dipartimento di Informatica
Download article
Open on HAL
Imported on
March 26, 2015
Published on
January 1, 2006
Last modified on
March 31, 2025
Volume 8
vol. 8
DOI
10.46298/dmtcs.361
License
https://about.hal.science/hal-authorisation-v1
Indicators
1225
Views
961
Downloads

Optimal L(h,k)-Labeling of Regular Grids

Tiziana Calamoneri ORCID (1)
(1) Dipartimento di Informatica
Abstract
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.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • L(h
  • k)-labeling
  • cellular grids
  • triangular grids
  • hexagonal grids
  • squared grids
Cited by

Source: OpenCitations

  • Optimal Real Number Graph Labellings of a Subfamily of Kneser Graphs

    SIAM Journal on Discrete Mathematics

    Authors : Rok Erman, Suzana Jurečič, Daniel Král' ORCID, Kris Stopar, Nik Stopar ORCID

    Journal reference : Volume 23, 2009, pp. 1372-1381

    DOI : 10.1137/060672923

  • Bounds for the Real Number Graph Labellings and Application to Labellings of the Triangular Lattice

    SIAM Journal on Discrete Mathematics

    Authors : Daniel Král' ORCID, Petr Škoda ORCID

    Journal reference : Volume 22, 2008, pp. 1559-1569

    DOI : 10.1137/07068552x

  • Distance two labellings for 8-regular grid

    International Journal of Computer Mathematics Computer Systems Theory

    Authors : Byeong Moon Kim ORCID, Byung Chul Song

    Journal reference : Volume 3, 2018, pp. 274-280

    DOI : 10.1080/23799927.2018.1545702

  • L(1, 2)-edge-labelings for lattices

    Applied mathematics/Applied Mathematics. A Journal of Chinese Universities/Gao-xiao yingyong shuxue xuebao

    Authors : Dan He ORCID, Wen-song Lin ORCID

    Journal reference : Volume 29, 2014, pp. 230-240

    DOI : 10.1007/s11766-014-3176-4

  • On the L(h,k)-Labeling of Co-comparability Graphs

    Lecture notes in computer science

    Authors : Tiziana Calamoneri ORCID, Saverio Caminiti, Stephan Olariu ORCID, Rossella Petreschi ORCID

    Journal reference : Volume , 2007, pp. 116-127

    DOI : 10.1007/978-3-540-74450-4_11

  • A General Approach to L(h,k)-Label Interconnection Networks

    Journal of Computer Science and Technology

    Authors : Tiziana Calamoneri ORCID, Saverio Caminiti, Rossella Petreschi ORCID

    Journal reference : Volume 23, 2008, pp. 652-659

    DOI : 10.1007/s11390-008-9161-8

  • L(2,1)-labeling of interval graphs

    Journal of Applied Mathematics and Computing

    Authors : Satyabrata Paul, Madhumangal Pal ORCID, Anita Pal ORCID

    Journal reference : Volume 49, 2014, pp. 419-432

    DOI : 10.1007/s12190-014-0846-6

  • Graph labellings with variable weights, a survey

    Discrete Applied Mathematics

    Authors : Jerrold R. Griggs, Daniel Král’ ORCID

    Journal reference : Volume 157, 2008, pp. 2646-2658

    DOI : 10.1016/j.dam.2008.08.024

  • On Irreducible No-hole L(2, 1)-labelings of Hypercubes and Triangular Lattices

    Lecture notes in computer science

    Authors : Nibedita Mandal ORCID, Pratima Panigrahi ORCID

    Journal reference : Volume , 2016, pp. 254-263

    DOI : 10.1007/978-3-319-29221-2_22

  • On -relaxed -labelings of the square lattice

    Information Processing Letters

    Authors : Benqiu Dai, Wensong Lin ORCID

    Journal reference : Volume 113, 2013, pp. 704-709

    DOI : 10.1016/j.ipl.2013.06.012

  • Multiple L(j,1)-labeling of the triangular lattice

    Journal of Combinatorial Optimization

    Authors : Pu Zhang ORCID, Wensong Lin ORCID

    Journal reference : Volume 27, 2012, pp. 695-710

    DOI : 10.1007/s10878-012-9549-9

  • On $$(s,t)$$ ( s , t ) -relaxed $$L(2,1)$$ L ( 2 , 1 ) -labelings of the triangular lattice

    Journal of Combinatorial Optimization

    Authors : Wensong Lin ORCID, Benqiu Dai

    Journal reference : Volume 29, 2013, pp. 655-669

    DOI : 10.1007/s10878-013-9615-y

  • L(j, k)-number of direct product of path and cycle

    Acta Mathematica Sinica English Series

    Authors : Wai Chee Shiu ORCID, Qiong Wu ORCID

    Journal reference : Volume 29, 2013, pp. 1437-1448

    DOI : 10.1007/s10114-013-2021-7

  • L(h,k)-labelling for octagonal grid

    International Journal of Computer Mathematics

    Authors : Byeong Moon Kim ORCID, Yoomi Rho, Byung Chul Song

    Journal reference : Volume 92, 2014, pp. 2243-2250

    DOI : 10.1080/00207160.2014.981536
Preview
Loading PDF preview...