Paweł Żyliński

Dr. Paweł Żyliński

Institute of Computer Science, University of Gdańsk, 80-308 Gdańsk, Poland

Research Focus & Metrics

Academic Career Length

22Years (2005-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
23 October 2018 in Aequationes mathematicae
Verified
Journal Article
Closed access
PDF file
PŻPaweł Żyliński
Paweł Żyliński

26 May 2017 in Graphs and Combinatorics
Verified
Journal Article
Closed access
PDF file
Magdalena LemańskaMagdalena Lemańska
Magdalena Lemańska
RZRita Zuazua
Rita Zuazua
PŻPaweł Żyliński
Paweł Żyliński

2 October 2018 in AKCE International Journal of Graphs and Combinatorics
Verified
Journal Article
Open access
PDF file
MDMagda Dettlaff
Magda Dettlaff
Magdalena LemańskaMagdalena Lemańska
Magdalena Lemańska
JTJerzy Topp
Jerzy Topp
RZRadosław Ziemann
Radosław Ziemann
PŻPaweł Żyliński
Paweł Żyliński
Imagine that we are given a set D of officials and a set W of civils. For each civil x∈W, there must be an official v∈D that can serve x, and whenever any such v is serving x, there must also be another civil w∈W that observes v, that is, w may act as a kind of witness, to avoid any abuse from v. What is the minimum number of officials to guarantee such a service, assuming a given social network? In this paper, we introduce the concept of certified domination that models the aforementioned problem. Specifically, a dominating set D of a graph G=(VG,EG) is said to be certified if every vertex in D has either zero or at least two neighbours in VG∖D. The cardinality of a minimum certified dominating set in G is called the certified domination number of G. Herein, we present the exact values of the certified domination number for some classes of graphs as well as provide some upper bounds on this parameter for arbitrary graphs. We then characterise a wide class of graphs with equal domination and certified domination numbers and characterise graphs with large values of certified domination numbers. Next, we examine the effects on the certified domination number when the graph is modified by deleting/adding an edge or a vertex. We also provide Nordhaus–Gaddum type inequalities for the certified domination number.

1 November 2020 in Discrete Mathematics
Verified
Journal Article
Closed access
RZRadosław Ziemann
Radosław Ziemann
PŻPaweł Żyliński
Paweł Żyliński

1 January 2006
Verified
Book Chapter
Closed access
PDF file
AKAdrian Kosowski
Adrian Kosowski
MMMichał Małafiejski
Michał Małafiejski
PŻPaweł Żyliński
Paweł Żyliński

31 July 2007 in Computational Geometry
Verified
Journal Article
Closed access
AKAdrian Kosowski
Adrian Kosowski
MMMichał Małafiejski
Michał Małafiejski
PŻPaweł Żyliński
Paweł Żyliński