RZRadosław Ziemann

Radosław Ziemann

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Radosław Ziemann has a total of 9 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • A linear time algorithm to compute vertices that belong to all, some and no minimum dominating sets in a tree and its consequences

    by Radosław Ziemann, Paweł Żyliński

    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.

  • A new approach to b-coloring of regular graphs

    by Magda Dettlaff, Hanna Furmańczyk, Iztok Peterin, Adriana Roux, Radosław Ziemann


  • Open Access

    A new approach to b-coloring of regular graphs

    by Magda Dettlaff, Hanna Furmańczyk, Iztok Peterin, Riana Roux, Radosław Ziemann

    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.

  • Graphs with equal domination and certified domination numbers

    by Magda Dettlaff, Magdalena Lemańska, Mateusz Miotk, Jerzy Topp, Radosław Ziemann, Paweł Żyliński

    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

    Certified domination

    by Magda Dettlaff, Magdalena Lemańska, Jerzy Topp, Radosław Ziemann, 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.