Temat: upper paired domination - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: The paired-domination and the upper paired-domination numbers of graphs
Autorzy:: Ulatowski, W.
Powiązania:: https://bibliotekanauki.pl/articles/255585.pdf
Data publikacji:: 2015
Wydawca:: Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:: paired-domination
paired-domination number
upper paired-domination number
Opis:: In this paper we continue the study of paired-domination in graphs. A paired-dominating set, abbreviated PDS, of a graph G with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of G, denoted by γP(G), is the minimum cardinality of a PDS of G. The upper paired-domination number of G, denoted by ΓP(G), is the maximum cardinality of a minimal PDS of G. Let G be a connected graph of order n ≥ 3. Haynes and Slater in [Paired-domination in graphs, Networks 32 (1998), 199-206], showed that γ P(G) ≤ n— 1 and they determine the extremal graphs G achieving this bound. In this paper we obtain analogous results for ΓP(G). Dorbec, Henning and McCoy in [Upper total domination versus upper paired-domination, Questiones Mathematicae 30 (2007), 1-12] determine Γp(Pn), instead in this paper we determine Γp(Cn). Moreover, we describe some families of graphs G for which the equality γP(G) = ΓP(G) holds.
Źródło:: Opuscula Mathematica; 2015, 35, 1; 127-135
1232-9274
2300-6919
Pojawia się w:: Opuscula Mathematica
Dostawca treści:: Biblioteka Nauki

Artykuł

Zmień widok

na półce

Skocz do pozycji: 2.

Tytuł:: Total domination versus paired domination
Autorzy:: Schaudt, Oliver
Powiązania:: https://bibliotekanauki.pl/articles/743224.pdf
Data publikacji:: 2012
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: total domination
upper total domination
paired domination
upper paired domination
generalized claw-free graphs
Opis:: A dominating set of a graph G is a vertex subset that any vertex of G either belongs to or is adjacent to. A total dominating set is a dominating set whose induced subgraph does not contain isolated vertices. The minimal size of a total dominating set, the total domination number, is denoted by γₜ. The maximal size of an inclusionwise minimal total dominating set, the upper total domination number, is denoted by Γₜ. A paired dominating set is a dominating set whose induced subgraph has a perfect matching. The minimal size of a paired dominating set, the paired domination number, is denoted by γₚ. The maximal size of an inclusionwise minimal paired dominating set, the upper paired domination number, is denoted by Γₚ.
In this paper we prove several results on the ratio of these four parameters: For each r ≥ 2 we prove the sharp bound γₚ/γₜ ≤ 2 - 2/r for $K_{1,r}$-free graphs. As a consequence, we obtain the sharp bound γₚ/γₜ ≤ 2 - 2/(Δ+1), where Δ is the maximum degree. We also show for each r ≥ 2 that ${C₅,T_r}$-free graphs fulfill the sharp bound γₚ/γₜ ≤ 2 - 2/r, where $T_r$ is obtained from $K_{1,r}$ by subdividing each edge exactly once. We show that all of these bounds also hold for the ratio Γₚ/Γₜ. Further, we prove that a graph hereditarily has an induced paired dominating set if and only if γₚ ≤ Γₜ holds for any induced subgraph. We also give a finite forbidden subgraph characterization for this condition. We exactly determine the maximal value of the ratio γₚ/Γₜ taken over the induced subgraphs of a graph. As a consequence, we prove for each r ≥ 3 the sharp bound γₚ/Γₜ ≤ 2 - 2/r for graphs that do not contain the corona of $K_{1,r}$ as subgraph. In particular, we obtain the sharp bound γₚ/Γₜ ≤ 2 - 2/Δ.
Źródło:: Discussiones Mathematicae Graph Theory; 2012, 32, 3; 435-447
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Zmień widok

na półce

Informacja

Wyszukujesz frazę "upper paired domination" wg kryterium: Temat

Źródło danych

Dostawca treści

Kolekcja

Rok wydania

Wydawca

Temat

Autor

Typ dokumentu

Język