Let \(j\) and \(k\) be two positive integers. An \(L(j,k)\)-labeling of a graph \(G\) is an assignment of nonnegative integers to the vertices of \(G\) such that the difference between labels of any two adjacent vertices is at least \(j\), and the difference between labels of any two vertices that are at distance two apart is at least \(k\). The minimum range of labels over all \(L(j,k)\)-labelings of a graph \(G\) is called the \(\lambda_{j,k}\)-number of \(G\), denoted by \(\lambda_{j,k}(G)\). Similarly, we can define \(L(j,k)\)-edge-labeling and \(L(j,k)\)-edge-labeling number, \(\lambda’_{j,k}(G)\), of a graph \(G\). In this paper, we show that if \(G\) is \(K_{1,3}\)-free with maximum degree \(\Delta\) then \(\lambda_{j,k}(G) \leq k\lfloor\Delta^2/2\rceil + j\Delta – 1\) except that \(G\) is a 5-cycle and \(j = k\). Consequently, we obtain an upper bound for \(\lambda’_{j,k}(G)\) in terms of the maximum degree of \(L(G)\), where \(L(G)\) is the line graph of \(G\). This improves the upper bounds for \(\lambda’_{2,1}(G)\) and \(\lambda’_{1,1}(G)\) given by Georges and Mauro [Ars Combinatoria \(70 (2004), 109-128]\). As a corollary, we show that Griggs and Yeh’s conjecture that \(\lambda_{2,1}(G) \leq \Delta^2\) holds for all \(K_{1,3}\)-free graphs and hence holds for all line graphs. We also investigate the upper bound for \(\lambda’_{j,k}(G)\) for \(K_{1,3}\)-free graphs \(G\).
1970-2025 CP (Manitoba, Canada) unless otherwise stated.