Anzeige
Erschienen in:
19.01.2021
Bounds on the semipaired domination number of graphs with minimum degree at least two
Erschienen in: Journal of Combinatorial Optimization | Ausgabe 2/2021
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Let G be a graph with vertex set V and no isolated vertices. A subset \(S \subseteq V\) is a semipaired dominating set of G if every vertex in \(V {\setminus } S\) is adjacent to a vertex in S and S can be partitioned into two element subsets such that the vertices in each subset are at most distance two apart. The semipaired domination number \(\gamma _\mathrm{pr2}(G)\) is the minimum cardinality of a semipaired dominating set of G. We show that if G is a connected graph of order n with minimum degree at least 2, then \(\gamma _\mathrm{pr2}(G) \le \frac{1}{2}(n+1)\). Further, we show that if \(n \not \equiv 3 \, (\mathrm{mod}\, 4)\), then \(\gamma _\mathrm{pr2}(G) \le \frac{1}{2}n\), and we show that for every value of \(n \equiv 3 \, (\mathrm{mod}\, 4)\), there exists a connected graph G of order n with minimum degree at least 2 satisfying \(\gamma _\mathrm{pr2}(G) = \frac{1}{2}(n+1)\). As a consequence of this result, we prove that every graph G of order n with minimum degree at least 3 satisfies \(\gamma _\mathrm{pr2}(G) \le \frac{1}{2}n\).