Anzeige
Erschienen in:
04.05.2019
A new lower bound on the domination number of a graph
Erschienen in: Journal of Combinatorial Optimization | Ausgabe 3/2019
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
A set S of vertices in a graph G is a dominating set of G if every vertex not in S is adjacent to some vertex in S. The domination number, \(\gamma (G)\), of G is the minimum cardinality of a dominating set of G. Lemańska (Discuss Math Graph Theory 24:165–170, 2004) showed that if T is a tree of order \(n \ge 2\) with \(\ell \) leaves, then \(\gamma (T) \ge (n-\ell +2)/3\), and characterized all trees achieving equality in this bound. In this paper, we first characterize all trees T of order n with \(\ell \) leaves satisfying \(\gamma (T) = \lceil (n - \ell + 2)/3 \rceil \). We then generalize this result to connected graphs and show that if G is a connected graph of order \(n \ge 2\) with \(k \ge 0\) cycles and \(\ell \) leaves, then \(\gamma (G) \ge \lceil (n-\ell +2 - 2k)/3 \rceil \). We also characterize the graphs G achieving equality for this new bound.