Radosław Ziemann
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Radosław Ziemann has a total of 9 co-authors. Here are the top co-authors by number of shared publications:
- Magda Dettlaff
Faculty of Applied Physics and Mathematics, Gdańsk University of Technology, Gdańsk, Poland
4 shared publications - Paweł Żyliński
University of Gdansk, Gdansk, Poland
3 shared publications - Hanna Furmańczyk
Institute of Informatics Faculty of Mathematics Physics and Informatics University of Gdańsk Gdańsk Poland
2 shared publications - Iztok Peterin
Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia
2 shared publications - Jerzy Topp
University of Gdansk, Gdansk, Poland
2 shared publications - Magdalena Lemańska
Gdansk University of Technology
2 shared publications
Latest Publications
- 1 January 2025
- Published by AGH University Press in Opuscula Mathematica
- p. 841-855
A linear time algorithm to compute vertices that belong to all, some and no minimum dominating sets in a tree and its consequences
We provide a linear time algorithm for determining the sets of vertices that belong to all, some and no minimum dominating sets of a tree, respectively, thus improving the quadratic time algorithm of Benecke and Mynhardt in 2008 [S. Benecke, C.M. Mynhardt, Trees with domination subdivision number one, Australas. J. Comb. 42 (2008), 201-209]. Some algorithmic consequences are also discussed.
- 1 January 2025
- Published by AGH University Press in Opuscula Mathematica
- p. 841-855
A linear time algorithm to compute vertices that belong to all, some and no minimum dominating sets in a tree and its consequences
We provide a linear time algorithm for determining the sets of vertices that belong to all, some and no minimum dominating sets of a tree, respectively, thus improving the quadratic time algorithm of Benecke and Mynhardt in 2008 [S. Benecke, C.M. Mynhardt, Trees with domination subdivision number one, Australas. J. Comb. 42 (2008), 201-209]. Some algorithmic consequences are also discussed.
- 9 July 2024
- Published by Elsevier in Applied Mathematics and Computation
- Vol. 481
A new approach to b-coloring of regular graphs
- 9 July 2024
- Published by Elsevier in Applied Mathematics and Computation
- Vol. 481
A new approach to b-coloring of regular graphs
- Open Access
A new approach to b-coloring of regular graphs
Let $G$ be a graph and c a proper k-coloring of G, i.e. any two adjacent vertices u and v have different colors c(u) and c(v). A proper k-coloring is a b-coloring if there exists a vertex in every color class that contains all the colors in its closed neighborhood. The maximum number of colors k admitting b-coloring of G is the b-chromatic number. We present two separate approaches to the conjecture posed by Blidia et. al that the b-chromatic number equals to d+1 for every d-regular graph of girth at least five except the Petersen graph.Open AccessA new approach to b-coloring of regular graphs
Let $G$ be a graph and c a proper k-coloring of G, i.e. any two adjacent vertices u and v have different colors c(u) and c(v). A proper k-coloring is a b-coloring if there exists a vertex in every color class that contains all the colors in its closed neighborhood. The maximum number of colors k admitting b-coloring of G is the b-chromatic number. We present two separate approaches to the conjecture posed by Blidia et. al that the b-chromatic number equals to d+1 for every d-regular graph of girth at least five except the Petersen graph. - 1 January 2019
- Published by AGH University Press in Opuscula Mathematica
- Vol. 39 (6) , 815-827
Graphs with equal domination and certified domination numbers
A set \(D\) of vertices of a graph \(G=(V_G,E_G)\) is a dominating set of \(G\) if every vertex in \(V_G-D\) is adjacent to at least one vertex in \(D\). The domination number (upper domination number, respectively) of \(G\), denoted by \(\gamma(G)\) (\(\Gamma(G)\), respectively), is the cardinality of a smallest (largest minimal, respectively) dominating set of \(G\). A subset \(D\subseteq V_G\) is called a certified dominating set of \(G\) if \(D\) is a dominating set of \(G\) and every vertex in \(D\) has either zero or at least two neighbors in \(V_G-D\). The cardinality of a smallest (largest minimal, respectively) certified dominating set of \(G\) is called the certified (upper certified, respectively) domination number of \(G\) and is denoted by \(\gamma_{\rm cer}(G)\) (\(\Gamma_{\rm cer}(G)\), respectively). In this paper relations between domination, upper domination, certified domination and upper certified domination numbers of a graph are studied.- 1 January 2019
- Published by AGH University Press in Opuscula Mathematica
- Vol. 39 (6) , 815-827
Graphs with equal domination and certified domination numbers
A set \(D\) of vertices of a graph \(G=(V_G,E_G)\) is a dominating set of \(G\) if every vertex in \(V_G-D\) is adjacent to at least one vertex in \(D\). The domination number (upper domination number, respectively) of \(G\), denoted by \(\gamma(G)\) (\(\Gamma(G)\), respectively), is the cardinality of a smallest (largest minimal, respectively) dominating set of \(G\). A subset \(D\subseteq V_G\) is called a certified dominating set of \(G\) if \(D\) is a dominating set of \(G\) and every vertex in \(D\) has either zero or at least two neighbors in \(V_G-D\). The cardinality of a smallest (largest minimal, respectively) certified dominating set of \(G\) is called the certified (upper certified, respectively) domination number of \(G\) and is denoted by \(\gamma_{\rm cer}(G)\) (\(\Gamma_{\rm cer}(G)\), respectively). In this paper relations between domination, upper domination, certified domination and upper certified domination numbers of a graph are studied.- Open Access
- 2 October 2018
- Published by Taylor & Francis in AKCE International Journal of Graphs and Combinatorics
- Vol. 17 (1) , 1-12
Certified domination
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.
- 2 October 2018
- Published by Taylor & Francis in AKCE International Journal of Graphs and Combinatorics
- Vol. 17 (1) , 1-12
Open AccessCertified domination
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.