Temat: semitotal domination - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: Vertices Contained In All Or In No Minimum Semitotal Dominating Set Of A Tree
Autorzy:: Henning, Michael A.
Marcon, Alister J.
Powiązania:: https://bibliotekanauki.pl/articles/31341173.pdf
Data publikacji:: 2016-02-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: domination
semitotal domination
trees
Opis:: Let G be a graph with no isolated vertex. In this paper, we study a parameter that is squeezed between arguably the two most important domination parameters; namely, the domination number, γ(G), and the total domination number, γ_t(G). A set S of vertices in a graph G is a semitotal dominating set of G if it is a dominating set of G and every vertex in S is within distance 2 of another vertex of S. The semitotal domination number, γ_t2(G), is the minimum cardinality of a semitotal dominating set of G. We observe that γ(G) ≤ γ_t2(G) ≤ γ_t(G). We characterize the set of vertices that are contained in all, or in no minimum semitotal dominating set of a tree.
Źródło:: Discussiones Mathematicae Graph Theory; 2016, 36, 1; 71-93
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

Tytuł:: The Semitotal Domination Problem in Block Graphs
Autorzy:: Henning, Michael A.
Pal, Saikat
Pradhan, D.
Powiązania:: https://bibliotekanauki.pl/articles/32361741.pdf
Data publikacji:: 2022-02-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: domination
semitotal domination
block graphs
undirected path graphs
NP-complete
Opis:: A set D of vertices in a graph G is a dominating set of G if every vertex outside D is adjacent in G to some vertex in D. A set D of vertices in G is a semitotal dominating set of G if D is a dominating set of G and every vertex in D is within distance 2 from another vertex of D. Given a graph G and a positive integer k, the semitotal domination problem is to decide whether G has a semitotal dominating set of cardinality at most k. The semitotal domination problem is known to be NP-complete for chordal graphs and bipartite graphs as shown in [M.A. Henning and A. Pandey, Algorithmic aspects of semitotal domination in graphs, Theoret. Comput. Sci. 766 (2019) 46–57]. In this paper, we present a linear time algorithm to compute a minimum semitotal dominating set in block graphs. On the other hand, we show that the semitotal domination problem remains NP-complete for undirected path graphs.
Źródło:: Discussiones Mathematicae Graph Theory; 2022, 42, 1; 231-248
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja