Labelling graphs with the circular difference
type: Item
instance of: scholarly article
title: Labelling graphs with the circular difference
zbMATH Open document ID: 0973.05065
author: Kun-Feng Wu
author: Roger K. Yeh
published in: Taiwanese Journal of Mathematics
publication date: 2001-10-22T00:00:00Z
review text: For positive integers \(k\) and \(d\geq 2\), a \(k\)-\(S(d,1)\)-labelling of a graph \(G\) is a function on the vertex set of \(G\), \(f: V(G)\to \{ 0,1,2,\dots ,k-1\} \), such that \[ |f(u)-f(v)|_k\geq \left\{\begin{matrix} d &\text{if} {d} _G(u,v)=1 \\ 1 &\text{if} {d} _G(u,v)=2\end{matrix}\right. \] where \(|x|_k=\min\{ |x|,k-|x|\} \) is the circular difference modulo \(k\). The \(\sigma _d\)-number of \(G\), \(\sigma _d(G)\), is the minimum \(k\) for which a \(k\)-\(S(d,1)\)-labelling of \(G\) exists and \(\sigma_d'd(G)\) is the minimum \(k\) for which an injective \(k\)-\(S'(d,1)\)-labelling of \(G\) exists. If the circular difference is replaced by the absolute difference, then \(f\) is an \(L(d,1)\)-labelling of \(G\). The span of an \(L(d,1)\)-labelling is the difference of the maximum and minimum labels used. The \(\lambda _d\)-number of \(G\), \(\lambda _d(G)\), is the minimum span among all \(L(d,1)\)-labellings of \(G\). A lower and an upper bound for \(\sigma _d(G)\) in terms of \(\lambda _d(G)\) is determined. The values of \(\sigma _d(G)\) for trees and cycles are also determined. Furthermore, the values of \(\sigma_d'(G)\) for joins of graphs and for complete multipartite graphs are determined.
Mathematics Subject Classification ID: 05C78
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C90
zbMATH DE Number: 1547612
zbMATH Keywords: graph labellings
zbMATH Keywords: circular difference
reviewed by: Dalibor Fronček
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.11650/twjm/1500407256
OpenAlex ID: W4245375765
DOI: 10.11650/TWJM/1500407256
description: scientific article; zbMATH DE number 1547612