L(2,1)-labeling of disk intersection graphs

Joanna Chybowska-Sokół , Konstanty Junosza-Szaniawski , Paweł Rzążewski

Abstract

In this paper we study the problem of L(2,1)-labeling of intersection graphs of disks. An L(2,1)-labeling is a mapping from the vertex set of the graph to non-negative integers, in which labels assigned to adjacent vertices differ by at least 2, and labels assigned to vertices at distance 2 are different. The span of an L(2,1)-labeling is the difference between the maximum and the minimum label used, and the span λ(G) of a graph G is the minimum span of an L(2,1)-labeling of G. We show that if G is an intersection graph of disks, then λ(G)≤[Formula presented]Δ2+25Δ+20. Moreover, if all disks in the geometric representation of G have equal radii, then λ(G)≤14Δ+11. We also present a refined upper bound for unit disk intersection graphs with small maximum degree.

Author Joanna Chybowska-Sokół (FMIS)
Joanna Chybowska-Sokół,,
- Faculty of Mathematics and Information Science
, Konstanty Junosza-Szaniawski (FMIS / DAC)
Konstanty Junosza-Szaniawski,,
- Department of Algebra and Combinatorics
, Paweł Rzążewski (FMIS / DIPS)
Paweł Rzążewski,,
- Department of Information Processing Systems
Journal seriesDiscrete Applied Mathematics, ISSN 0166-218X, e-ISSN 1872-6771
Issue year2020
Vol277
Pages71-81
Keywords in Polishgraf przecięć dysków, L(2,1)-etykietowanie
Keywords in Englishdisk graph, L(2,1)-labeling
ASJC Classification2604 Applied Mathematics; 2607 Discrete Mathematics and Combinatorics
Abstract in PolishW pracy rozważamy L(2,1)-etykietowanie grafów przecięć dysków. W szczególności interesuje nas “hipoteza Delta kwadrat” Griggsa i Yeha, zajmująca się pytaniem czy każdy graf można L(2,1)-etykietować przy zachowaniu ograniczenia na maksymalną etykietę λ(G) ≤ ∆^2, gdzie ∆ oznacza maksymalny stopień grafu. Dowodzimy, że dla grafów przecięć dysków λ(G) ≤ 4/5∆^2 + 25∆ + 20, co dowodzi hipotezy dla grafów dyskowych o maksymalnym stopniu ∆>=126. W przypadku grafów przecięć dysków jednostkowych, wprowadzamy dwa nowe ograniczenia górne: λ(G) ≤ 3/4∆^2 + 3∆-3 oraz λ(G) ≤ 14∆ + 11, dowodząc hipotezy dla grafów UDG spełniających ∆>=11.
DOIDOI:10.1016/j.dam.2019.08.020
URL https://www.sciencedirect.com/science/article/pii/S0166218X19303932
Languageen angielski
Score (nominal)70
Score sourcejournalList
ScoreMinisterial score = 70.0, 09-07-2020, ArticleFromJournal
Publication indicators Scopus Citations = 0; Scopus SNIP (Source Normalised Impact per Paper): 2018 = 1.263; WoS Impact Factor: 2018 = 0.983 (2) - 2018=1.029 (5)
Citation count*
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back
Confirmation
Are you sure?