Distance irredundance and connected domination numbers of a graph

Jun Ming Xu, Fang Tian, Jia Huang

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


Let k be a positive integer and G be a connected graph. This paper considers the relations among four graph theoretical parameters: the k-domination number γk (G), the connected k-domination number γkc (G); the k-independent domination number γki (G) and the k-irredundance number irk (G). The authors prove that if an irk-set X is a k-independent set of G, then irk (G) = γk (G) = γki (G), and that for k ≥ 2, γkc (G) = 1 if irk (G) = 1, γkc (G) ≤ max { (2 k + 1) irk (G) - 2 k, frac(5, 2) irk (G) k - frac(7, 2) k + 2 } if irk (G) is odd, and γkc (G) ≤ frac(5, 2) irk (G) k - 3 k + 2 if irk (G) is even, which generalize some known results.

Original languageEnglish (US)
Pages (from-to)2943-2953
Number of pages11
JournalDiscrete Mathematics
Issue number22
StatePublished - Nov 28 2006
Externally publishedYes


  • Connected k-domination number
  • k-Domination number
  • k-Independent domination number
  • k-Independent set
  • k-Irredundance number

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Distance irredundance and connected domination numbers of a graph'. Together they form a unique fingerprint.

Cite this