Paried-domination Number In Cubic Graphs

A paired-dominating set of a graph G is a dominating set of vertices whose induced subgraph has a perfect matching, while the paired-domination number, de-noted by γpr(G), is the minimum cardinality of a paired-dominating set in G. Chen, Sun and Xing [Acta Mathematica scientia Series A Chinese Edition27(1)(2007)] proved that a cubic graph has paired-domination number at most3/5the number of vertices in the graph, and they posed a conjecture about γpr(G):if G is a con-nected graph of order n≥11with minimum degree at least3, then γpr9G)≤4n/7. Goddard and Henning [A characterization of cubic graphs with paired-domination number three-fifths their order, Graphs and Combinatorics(2009)25:675-692] fur-ther showed that the Petersen graph is the only connected cubic graph with paired-domination number three-fifths its order and they posed a stronger conjecture:if G≠P is a connected graph of order n with6(G)≥3, then γpr(G)≤4n/7. In this paper we investigate the paired-domination number in cubic graphs. Specifically, we show that γpr(G)≤An/7if G is a connected cubic graph of order n, with the exception of Petersen graph.