Uniformly pair-bonded trees

Wai Chee Shiu*, Xue Gang Chen, Wai Hong Chan

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

1 Citation (Scopus)


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 bp(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 bp(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 bp(T) = k for any positive integer k. Furthermore, we give a constructive characterization of uniformly pair-bonded trees.

Original languageEnglish
Pages (from-to)71-78
Number of pages8
JournalArs Combinatoria
Publication statusPublished - Jan 2010

Scopus Subject Areas

  • Mathematics(all)

User-Defined Keywords

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


Dive into the research topics of 'Uniformly pair-bonded trees'. Together they form a unique fingerprint.

Cite this