Discrete Mathematics & Theoretical Computer Science,Vol 10, No 1 (2008)

摘要

A dominating set D of vertices in a graph G is called anefficient dominating set if the distance between any two verticesin D is at least three. A tree T of order n is calledmaximum if T has the largest number of efficient dominating setsamong all n-vertex trees. A constructive characterization of allmaximum trees is given. Their structure has recurring aspects withperiod 7. Moreover, the number of efficient dominating sets inmaximum n-vertex trees is determined and appears to beexponential. Also the number of maximum n-vertex trees is shownto be bounded below by an increasing exponential function in n.