Advertisement
Published in:
04-05-2019
A new lower bound on the domination number of a graph
Published in: Journal of Combinatorial Optimization | Issue 3/2019
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.