Uniformly pair-bonded trees

Wai Chee SHIU, Xue-Gang CHEN, Wai Hong CHAN

Research output: Contribution to journalArticles

1 Citation (Scopus)

Abstract

Let G = (V(G), E(G)) be a graph with δ(G) ≥ 1. A set DV(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 ϒᵨ(G), is the minimum cardinality of a paired-dominating set of G. The paired bondage number, denoted by bᵨ(G), is the minimum cardinality among all sets of edges ⊆ E such that δ(G-) ≥ 1 and ϒᵨ(G-) ˃ ϒᵨ(G). For any bᵨ(G) edges ⊆ E with δ(G-) ≥ 1, if ϒᵨ(G-) ˃ ϒᵨ(G), then G is called uniformly pair-bonded graph. In this paper, we prove that there exists uniformly pair-ponded tree T with bᵨ(T) = k for any positive integer k. Furthermore, we give a constructive characterization of uniformly pair-bonded trees. Copyright © 2010 Dept. of Combinatorics and Optimization, University of Waterloo
Original languageEnglish
Pages (from-to)71-78
JournalArs Combinatoria
Volume94
Publication statusPublished - 2010

Citation

Shiu, W. C., Chen, X.-G., & Chan, W. H. (2010). Uniformly pair-bonded trees. Ars Combinatoria, 94, 71-78.

Keywords

  • Domination number
  • Paired-domination number
  • Paired bondage number
  • Uniformly pair-bonded graph

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