Joanna Raczek - Publications - Bridge of Knowledge

Search

Profile photo: dr inż. Joanna Raczek

dr inż. Joanna Raczek

Filters

total: 39

  • Category
  • Year
  • Options

clear Chosen catalog filters disabled

Catalog Publications

Year 2024
  • Potyczki algorytmiczne, czyli Alicja i Bogdan w nowych sytuacjach
    Publication

    - Pismo PG - Year 2024

    W kolejnym odcinku serii z Alicją i Bogdanem najpierw ilustrujemy problem dominowania w grafach (kratowych): klasyczny i rzymski. Następnie ilustrujemy znany fakt, że zachłanność nie zawsze się opłaca. Pokażemy mianowicie, że algorytmy zachłanne nie gwarantują uzyskania rozwiązania optymalnego, nawet wówczas gdy problem da się rozwiązać w czasie wielomianowym.

    Full text to download in external service

Year 2023
  • Complexity Issues on of Secondary Domination Number
    Publication

    - ALGORITHMICA - Year 2023

    In this paper we study the computational complexity issues of the problem of secondary domination (known also as (1, 2)-domination) in several graph classes. We also study the computational complexity of the problem of determining whether the domination and secondary domination numbers are equal. In particular, we study the influence of triangles and vertices of degree 1 on these numbers. Also, an optimal algorithm for finding...

    Full text available to download

Year 2022
  • Application of Doubly Connected Dominating Sets to Safe Rectangular Smart Grids
    Publication

    - ENERGIES - Year 2022

    Smart grids, together with the Internet of Things, are considered to be the future of the electric energy world. This is possible through a two-way communication between nodes of the grids and computer processing. It is necessary that the communication is easy and safe, and the distance between a point of demand and supply is short, to reduce the electricity loss. All these requirements should be met at the lowest possible cost....

    Full text available to download

  • Paired domination versus domination and packing number in graphs
    Publication

    Given a graph G = (V(G), E(G)), the size of a minimum dominating set, minimum paired dominating set, and a minimum total dominating set of a graph G are denoted by γ (G), γpr(G), and γt(G), respectively. For a positive integer k, a k-packing in G is a set S ⊆ V(G) such that for every pair of distinct vertices u and v in S, the distance between u and v is at least k + 1. The k-packing number is the order of a largest kpacking and...

    Full text available to download

  • Polynomial Algorithm for Minimal (1,2)-Dominating Set in Networks
    Publication

    - Electronics - Year 2022

    Dominating sets find application in a variety of networks. A subset of nodes D is a (1,2)-dominating set in a graph G=(V,E) if every node not in D is adjacent to a node in D and is also at most a distance of 2 to another node from D. In networks, (1,2)-dominating sets have a higher fault tolerance and provide a higher reliability of services in case of failure. However, finding such the smallest set is NP-hard. In this paper, we...

    Full text available to download

Year 2021
  • Block graphs with large paired domination multisubdivision number
    Publication

    - Discussiones Mathematicae Graph Theory - Year 2021

    The paired domination multisubdivision number of a nonempty graph G, denoted by msdpr(G), is the smallest positive integer k such that there exists an edge which must be subdivided k times to increase the paired domination number of G. It is known that msdpr(G) ≤ 4 for all graphs G. We characterize block graphs with msdpr(G) = 4.

    Full text available to download

  • Grafy w Imperium Rzymskim
    Publication

    - Pismo PG - Year 2021

    Teoria grafów znalazła zastosowanie w sieciach telekomunikacyjnych, transporcie, bioinformatyce, zarządzaniu i w wielu innych dziedzinach. Ale co ma ona wspólnego z Imperium Rzymskim?

    Full text available to download

  • Komputer w labiryncie

    Programiści piszą programy, które potrafią robić wiele różnych rzeczy: odtwarzać filmy, prognozować pogodę, pomagać w nauce języków obcych czy matematyki. Ale czy wiesz, że można zaprogramować komputer tak, aby tworzył labirynty? W dodatku takie, które zawierają tajne informacje!

    Full text available to download

  • Progress on Roman and Weakly Connected Roman Graphs
    Publication

    - Mathematics - Year 2021

    A graph G for which γR(G)=2γ(G) is the Roman graph, and if γwcR(G)=2γwc(G), then G is the weakly connected Roman graph. In this paper, we show that the decision problem of whether a bipartite graph is Roman is a co-NP-hard problem. Next, we prove similar results for weakly connected Roman graphs. We also study Roman trees improving the result of M.A. Henning’s A characterization of Roman trees, Discuss. Math. Graph Theory 22 (2002)....

    Full text available to download

Year 2020
Year 2019
  • Domination subdivision and domination multisubdivision numbers of graphs

    The domination subdivision number sd(G) of a graph G is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number of G. It has been shown [10] that sd(T)<=3 for any tree T. We prove that the decision problem of the domination subdivision number is NP-complete even for bipartite graphs. For this reason we define the domination multisubdivision number...

    Full text available to download

  • Weakly connected Roman domination in graphs
    Publication

    A Roman dominating function on a graph G=(V,E) is defined to be a function f :V → {0,1,2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v)=2. A dominating set D⊆V is a weakly connected dominating set of G if the graph (V,E∩(D×V)) is connected. We define a weakly connected Roman dominating function on a graph G to be a Roman dominating function such that the set...

    Full text available to download

Year 2018
  • On domination multisubdivision number of unicyclic graphs
    Publication

    The paper continues the interesting study of the domination subdivision number and the domination multisubdivision number. On the basis of the constructive characterization of the trees with the domination subdivision number equal to 3 given in [H. Aram, S.M. Sheikholeslami, O. Favaron, Domination subdivision number of trees, Discrete Math. 309 (2009), 622–628], we constructively characterize all connected unicyclic graphs with...

    Full text available to download

  • Total domination in versus paired-domination in regular graphs

    A subset S of vertices of a graph G is a dominating set of G if every vertex not in S has a neighbor in S, while S is a total dominating set of G if every vertex has a neighbor in S. If S is a dominating set with the additional property that the subgraph induced by S contains a perfect matching, then S is a paired-dominating set. The domination number, denoted γ(G), is the minimum cardinality of a dominating set of G, while the...

    Full text available to download

  • Total Domination Versus Domination in Cubic Graphs
    Publication

    A dominating set in a graph G is a set S of vertices of G such that every vertex not in S has a neighbor in S. Further, if every vertex of G has a neighbor in S, then S is a total dominating set of G. The domination number,γ(G), and total domination number, γ_t(G), are the minimum cardinalities of a dominating set and total dominating set, respectively, in G. The upper domination number, \Gamma(G), and the upper total domination...

    Full text available to download

Year 2016
Year 2015
  • Unicyclic graphs with equal total and total outer-connected domination numbers
    Publication

    - ARS COMBINATORIA - Year 2015

    Let G = (V,E) be a graph without an isolated vertex. A set D ⊆ V (G) is a total dominating set if D is dominating and the in- duced subgraph G[D] does not contain an isolated vertex. The total domination number of G is the minimum cardinality of a total domi- nating set of G. A set D ⊆ V (G) is a total outer–connected dominating set if D is total dominating and the induced subgraph G[V (G)−D] is a connected graph. The total outer–connected...

    Full text to download in external service

Year 2014
  • Some Progress on Total Bondage in Graphs
    Publication

    - GRAPHS AND COMBINATORICS - Year 2014

    The total bondage number b_t(G) of a graph G with no isolated vertex is the cardinality of a smallest set of edges E'⊆E(G) for which (1) G−E' has no isolated vertex, and (2) γ_t(G−E')>γ_t(G). We improve some results on the total bondage number of a graph and give a constructive characterization of a certain class of trees achieving the upper bound on the total bondage number.

    Full text to download in external service

Year 2013
  • Total restrained bondage in graphs
    Publication

    - ACTA MATHEMATICA SINICA-ENGLISH SERIES - Year 2013

    Podzbiór D zbioru wierzchołków grafu nazywamy zewnętrznie totalnym dominującym w grafie, jeśli każdy wierzchołek spoza D ma sąsiada zarówno w D jak i poza D. Moc najmniejszego zbioru o tej własności nazywamy liczbą dominowania zewnętrznie totalnego. W artykule badamy wpływ usuwania krawędzi na liczbę dominowania zewnętrznie totalnego, czyli liczbę zewnętrznego totalnego zniewolenie w grafach.

    Full text to download in external service

Year 2011
Year 2010
Year 2009
Year 2008
  • Distance paired domination numbers of graphs
    Publication

    W pracy przedstawione są pewne własności liczb k-dominowania parami w grafach. Wykazane jest, że problem decyzyjny liczby k-dominowania parami jest problemem NP-zupełnym nawet dla grafów dwudzielnych. Przedstawione są ograniczenia górne i dolne dla liczby k-dominowania parami w drzewach i scharakteryzowane drzewa, w których te ograniczenia są osiągnięte.

    Full text to download in external service

  • Paired bondage in trees
    Publication

    W pracy zdefiniowano pojęcie liczby zniewolenia parami jako moc najmniejszego zbioru krawędzi, którego usunięcie z grafu spowoduje wzrost liczby dominowania parami. W szczególności scharakteryzowane są wszystkie drzewa, w których liczba zniewolenia wynosi 0, czyli takie, w których usunięcie dowolnego podzbioru krawędzi nie zwiększy liczby dominowania parami.

    Full text to download in external service

  • Total restrained domination numbers of trees
    Publication

    Opisane są wszystkie drzewa, w których liczby dominowania totalnego i totalno - powściągniętego są sobie równe, a także podano dolne ograniczenie na liczbę dominowania totalno - powściągniętego w drzewach.

    Full text to download in external service

  • Weakly connected domination subdivision numbers

    Liczba podziału krawędzi dla dominowania słabo spójnego to najmniejsza liczba krawędzi jaką należy podzielić, aby wzrosła liczba dominowania słabo wypukłego. W pracy przedstawione są własności liczby podziału krawędzi dla dominowania słabo spójnego dla różnych grafów.

    Full text available to download

Year 2007
Year 2006
Year 2004
  • NP-completeness of convex and weakly convex domiating set decision problems.
    Publication

    Liczby dominowania wypukłego i słabo wypukłego są nowymi rodzajami liczb dominowania. W tym artykule pokazujemy, że problemy decyzyjne dominowania wypukłegi i słabo wypukłego są NP-zupełne w przypadku grafów dwudzielnych oraz split grafów. Posługując się zmodyfikowanym algorytmem Washalla możemy w czasie wielomianowym określić, czy dany podzbiór wierzchołków grafu jest spójny bądź słabo spójny.

    Full text available to download

seen 9855 times