## Abstract

The domination number γ(G) and the total domination number γ_{t}(G) of a graph G are generalized to the K_{n}-domination number γ_{Kn}(G) and the total K_{n}-domination number γ^{t}_{Kn}(G) for n≥2, where γ(G)=γ_{K2}(G) and γ_{t}(G)=γ^{t}_{K2}(G). K_{n}-connectivity is defined and, for every integer n≥2, the existence of a K_{n}-connected graph G of order at least n+1 for which γ_{K2}(G)+γ^{t}_{Kn}(G)=( (3n- 2) n^{2})p(G) is established. We conjecture that, if G is a K_{n}-connected graph of order at least n+1, then γ_{Kn}(G)+γ^{t}_{Kn}(G)≤( (3n-2) n^{2})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 K_{3}-connected graph of order at least 4 that satisfies the condition that, for each edge e of G, G-e contains at least one K_{3}-isolated vertex, then γ_{K3}(G)+γ^{t}_{K3 }(G)≤(3p) 4 and we show that this bound is best possible.

Original language | English |
---|---|

Pages (from-to) | 93-105 |

Number of pages | 13 |

Journal | Discrete Mathematics |

Volume | 120 |

Issue number | 1-3 |

DOIs | |

Publication status | Published - 12 Sept 1993 |

Externally published | Yes |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics