On \(L(2,1)\)-labelings of Cartesian products of paths and cycles
type: Item
instance of: scholarly article
title: On \(L(2,1)\)-labelings of Cartesian products of paths and cycles
zbMATH Open document ID: 1043.05104
author: Yanyan Li
published in: Discrete Mathematics
publication date: 2004-08-06T00:00:00Z
review text: An \(L(2,1)\)-labeling, also often called \(\lambda\)-coloring, is a function that assigns each vertex \(v\) in a graph \(G=(V,E)\) a nonnegative integer label, such that adjacent vertices have labels that differ by at least two, and vertices at distance two have different labels. The \(L(2,1)\)-labeling number of a graph \(G\) is the smallest \(k\) such that \(G\) has an \(L(2,1)\)-labeling with labels in \(\{0,1,\ldots, k\}\). This paper looks at the \(L(2,1)\)-labeling numbers of Cartesian products of paths and cycles. These can be seen as grid graphs with a number of wrap-around edges along the borders. The paper gives a complete classification for the product of one cycle and one path; and many results for the product of two cycles.
Mathematics Subject Classification ID: 05C78
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 2083726
zbMATH Keywords: \(L(2,1)\)-labeling
zbMATH Keywords: \(L(2,1)\)-labeling number
zbMATH Keywords: Cartesian product
zbMATH Keywords: path
zbMATH Keywords: cycle
zbMATH Keywords: grid
zbMATH Keywords: lambda-coloring
reviewed by: Hans L. Bodlaender
MaRDI profile type: Publication
full work available at URL: j.disc.2003.11.009
OpenAlex ID: W1990710940
cites work: On \(L(d,1)\)-labelings of graphs
cites work: The $L(2,1)$-Labeling Problem on Graphs
cites work: Q5466046
cites work: Distance-two labelings of graphs
cites work: Fixed-parameter complexity of \(\lambda\)-labelings
cites work: Q4863434
cites work: Q3838194
cites work: Q4879166
cites work: Q4949819
cites work: Labeling products of complete graphs with a condition at distance two
cites work: Relating path coverings to vertex labellings with a condition at distance two
cites work: Labelling Graphs with a Condition at Distance 2
cites work: Graph labeling and radio channel assignment
cites work: Optimal \(L(2,1)\)-labeling of Cartesian products of cycles, with an application to independent domination
cites work: Q4552180
cites work: Hamiltonicity and circular distance two labellings
cites work: Q5463346
cites work: Q4940064
cites work: Q5466031
cites work: Labeling Chordal Graphs: Distance Two Condition
cites work: On the $\lambda$-Number of $Q_n $ and Related Graphs
cites work: Labelling graphs with the circular difference
cites work: The edge span of distance two labellings of graphs
DOI: 10.1016/J.DISC.2003.11.009
description: scientific article; zbMATH DE number 2083726