## Abstract

Let G = (V(G), E(G)) be a graph with δ(G) ≥ 1. A set D ⊆ V(G) is a paired-dominating set if D is a dominating set and the induced subgraph G[D] contains a perfect matching. The paired domination number of G, denoted by γ_{P}(G), is the minimum cardinality of a paired-dominating set of G. The paired bondage number, denoted by b_{p}(G), is the minimum cardinality among all sets of edges E′ ⊆ E such that δ(G - E′) ≥1 and γ_{p}(G - E′) > γ_{p}(G). For any b_{p}(G) edges E′ ⊆ E with δ(G - E′) ≥ 1, if γ_{p}(G - E′) > γ_{p}(G), then G is called uniformly pair-bonded graph. In this paper, we prove that there exists uniformly pair-bonded tree T with b_{p}(T) = k for any positive integer k. Furthermore, we give a constructive characterization of uniformly pair-bonded trees.

Original language | English |
---|---|

Pages (from-to) | 71-78 |

Number of pages | 8 |

Journal | Ars Combinatoria |

Volume | 94 |

Publication status | Published - Jan 2010 |

## Scopus Subject Areas

- Mathematics(all)

## User-Defined Keywords

- Domination number
- Paired bondage number
- Paired-domination num-ber
- Uniformly pairbonded graph