Bounds relating generalized domination parameters

Michael A. Henning, Henda C. Swart

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


The domination number γ(G) and the total domination number γt(G) of a graph G are generalized to the Kn-domination number γKn(G) and the total Kn-domination number γtKn(G) for n≥2, where γ(G)=γK2(G) and γt(G)=γtK2(G). Kn-connectivity is defined and, for every integer n≥2, the existence of a Kn-connected graph G of order at least n+1 for which γK2(G)+γtKn(G)=( (3n- 2) n2)p(G) is established. We conjecture that, if G is a Kn-connected graph of order at least n+1, then γKn(G)+γtKn(G)≤( (3n-2) n2)p(G). This conjecture generalizes the result for n=2 of Allan, Laskar and Hedetniemi. We prove the conjecture for n=3. Further, it is shown that if G is a K3-connected graph of order at least 4 that satisfies the condition that, for each edge e of G, G-e contains at least one K3-isolated vertex, then γK3(G)+γtK3 (G)≤(3p) 4 and we show that this bound is best possible.

Original languageEnglish
Pages (from-to)93-105
Number of pages13
JournalDiscrete Mathematics
Issue number1-3
Publication statusPublished - 12 Sept 1993
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Bounds relating generalized domination parameters'. Together they form a unique fingerprint.

Cite this