Paired-domination in inflated graphs

Liying Kang, Moo Young Sohn, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

27 Citations (Scopus)


The inflation GIof a graph G with n(G) vertices and m(G) edges is obtained from G by replacing every vertex of degree d of G by a clique Kd. A set S of vertices in a graph G is a paired dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The paired domination number γp(G) is the minimum cardinality of a paired dominating set of G. In this paper, we show that if a graph G has a minimum degree δ(G)≥2, then n(G)≤γp(GI)≤4m(G)/ [δ(G)+1], and the equality γp(GI)=n(G) holds if and only if G has a perfect matching. In addition, we present a linear time algorithm to compute a minimum paired-dominating set for an inflation tree.
Original languageEnglish
Pages (from-to)485-494
Number of pages10
JournalTheoretical Computer Science
Issue number2-3
Publication statusPublished - 14 Jun 2004


  • Domination
  • Inflated graphs
  • Perfect matching

ASJC Scopus subject areas

  • Computational Theory and Mathematics


Dive into the research topics of 'Paired-domination in inflated graphs'. Together they form a unique fingerprint.

Cite this