Wyniki wyszukiwania dla: ROMAN DOMINATION

• Weakly connected Roman domination in graphs

  Publikacja

  • J. Raczek
  • J. Cyman

  - DISCRETE APPLIED MATHEMATICS - Rok 2019

  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...

  Pełny tekst do pobrania w portalu

• Analecta Romana Instituti Danici. Roma

  Czasopisma

  ISSN: 0066-1392

• Paired domination and doubly domination in graphs

  Publikacja

  • J. Raczek

  - Rok 2007

  W rozprawie poruszane są zagadnienia związane z dominowaniem parami w grafach oraz domiowaniem totalno - powściągniętym w grafach. Ponadto omawiane są zagadnienia związane ze złożonością obliczeniową różnych problemów dominowania w grafach.

• Domination subdivision and domination multisubdivision numbers of graphs

  Publikacja

  • M. Dettlaff
  • J. Raczek
  • J. Topp

  - Discussiones Mathematicae Graph Theory - Rok 2019

  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...

  Pełny tekst do pobrania w portalu

• Total Domination Versus Domination in Cubic Graphs

  Publikacja

  • J. Cyman
  • M. Dettlaff
  • M. A. Henning
  • M. Lemańska
  • J. Raczek

  - GRAPHS AND COMBINATORICS - Rok 2018

  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...

  Pełny tekst do pobrania w portalu

• Graphs with equal domination and certified domination numbers

  Publikacja

  • M. Dettlaff
  • M. Lemańska
  • J. Topp
  • M. Miotk
  • R. Ziemann
  • P. Żyliński

  - Opuscula Mathematica - Rok 2019

  A setDof vertices of a graphG= (VG,EG) is a dominating set ofGif every vertexinVG−Dis adjacent to at least one vertex inD. The domination number (upper dominationnumber, respectively) ofG, denoted byγ(G) (Γ(G), respectively), is the cardinality ofa smallest (largest minimal, respectively) dominating set ofG. A subsetD⊆VGis calleda certified dominating set ofGifDis a dominating set ofGand every vertex inDhas eitherzero...

  Pełny tekst do pobrania w portalu

• The paired-domination and the upper paired-domination numbers of graphs

  Publikacja

  • W. Ulatowski

  - Opuscula Mathematica - Rok 2015

  In this paper we obtain the upper bound for the upper paired-domination number and we determine the extremal graphs achieving this bound. Moreover we determine the upper paired- domination number for cycles.

  Pełny tekst do pobrania w portalu

• Paired domination versus domination and packing number in graphs

  Publikacja

  • M. Dettlaff
  • D. Gözüpek
  • J. Raczek

  - JOURNAL OF COMBINATORIAL OPTIMIZATION - Rok 2022

  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...

  Pełny tekst do pobrania w portalu

• Total domination in versus paired-domination in regular graphs

  Publikacja

  • J. Cyman
  • M. Dettlaff
  • M. A. Henning
  • M. Lemańska
  • J. Raczek

  - Discussiones Mathematicae Graph Theory - Rok 2018

  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...

  Pełny tekst do pobrania w portalu

• Graphs with equal domination and 2-distance domination numbers

  Publikacja

  • J. Raczek

  - Discussiones Mathematicae Graph Theory - Rok 2011

  W publikacji scharakteryzowane są wszystkie te drzewa i grafy jednocykliczne, w których liczba dominowania oraz liczba 2-dominowania na odległość są sobie równe.

  Pełny tekst do pobrania w portalu