Wyniki wyszukiwania dla: PAIRED DOMINATION

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

• 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

• 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

• Distance paired domination numbers of graphs

  Publikacja

  • J. Raczek

  - DISCRETE MATHEMATICS - Rok 2008

  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.

  Pełny tekst do pobrania w serwisie zewnętrznym

• Lower bound on the paired domination number of a tree

  Publikacja

  • J. Raczek

  - Australasian Journal of Combinatorics - Rok 2006

  W pracy przedstawione jest ograniczenie dolne dla liczby dominowania parami oraz scharakteryzowane są wszystkie drzewa ekstremalne.

  Pełny tekst do pobrania w portalu

• Paired domination subdivision and multisubdivision numbers of graphs

  Publikacja

  • J. Raczek
  • M. Dettlaff

  - Journal of Combinatorial Mathematics and Combinatorial Computing - Rok 2020

  The paired domination subdivision number sdpr(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 paired domination number of G. We prove that the decision problem of the paired domination subdivision number is NP-complete even for bipartite graphs. For this reason we define the paired domination muttisubdivision number of a nonempty graph...

  Pełny tekst do pobrania w portalu

• Block graphs with large paired domination multisubdivision number

  Publikacja

  • C. M. Mynhardt
  • J. Raczek

  - Discussiones Mathematicae Graph Theory - Rok 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.

  Pełny tekst do pobrania w portalu

• All graphs with paired-domination number two less than their order

  Publikacja

  • W. Ulatowski

  - Opuscula Mathematica - Rok 2013

  Let G=(V,E) be a graph with no isolated vertices. A set S⊆V is a paired-dominating set of G if every vertex not in S is adjacent with some vertex in S and the subgraph induced by S contains a perfect matching. The paired-domination number γp(G) of G is defined to be the minimum cardinality of a paired-dominating set of G. Let G be a graph of order n. In [Paired-domination in graphs, Networks 32 (1998), 199-206] Haynes and Slater...

  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