Article ID Journal Published Year Pages File Type
4650380 Discrete Mathematics 2008 5 Pages PDF
Abstract

A paired-dominating set   of a graph G=(V,E)G=(V,E) with no isolated vertex is a dominating set of vertices inducing a graph with a perfect matching. The paired-domination number   of GG, denoted by γpr(G)γpr(G), is the minimum cardinality of a paired-dominating set of GG. We consider graphs of order n≥6n≥6, minimum degree δδ such that GG and G¯ do not have an isolated vertex and we prove that–if γpr(G)>4γpr(G)>4 and γpr(G¯)>4, then γpr(G)+γpr(G¯)≤3+min{δ(G),δ(G¯)}.–if δ(G)≥2δ(G)≥2 and δ(G¯)≥2, then γpr(G)+γpr(G¯)≤2n3+4 and γpr(G)+γpr(G¯)≤2n3+2 if moreover n≥21n≥21.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,