## Abstract

Let G = (V,E) be a graph. A set S ⊆ V is a dominating set if every vertex of V - S is adjacent to some vertex in S. The domination number γ(G) of G is the minimum cardinality of a dominating set of G. A dominating set D is a least dominating set if γ(〈D〉) ≤ γ(〈S〉) for any dominating set S, and γ_{ℓ}(G) is the minimum cardinality of a least dominating set. Sampathkumar (Discrete Math. 86 (1990) 137-142) conjectured that γ_{ℓ}(G) < 3n/5 for every connected graph on n ≥ 2 vertices. This conjecture was proven by Favaron (Discrete Math. 150 (1996) 115-122). We shall characterise graphs G of order n that are edge-minimal with respect to satisfying G connected and γ_{ℓ}(G) = 3n/5. Furthermore, we construct a family of graphs G of order n that are not cycles and are edge-minimal with respect to satisfying G connected, δ(G) ≥ 2 and γ_{ℓ}(G) = 3n/5.

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

Pages (from-to) | 153-168 |

Number of pages | 16 |

Journal | Discrete Mathematics |

Volume | 216 |

Issue number | 1-3 |

DOIs | |

Publication status | Published - 6 Apr 2000 |

Externally published | Yes |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics