Dorota Bród ; Zdzisław Skupień - Recurrence among trees with most numerous efficient dominating sets

dmtcs:445 - Discrete Mathematics & Theoretical Computer Science, January 1, 2008, Vol. 10 no. 1 - https://doi.org/10.46298/dmtcs.445
Recurrence among trees with most numerous efficient dominating setsArticle

Authors: Dorota Bród 1; Zdzisław Skupień 2

  • 1 Faculty of Mathematics and Applied Physics [Rzeszow]
  • 2 Faculty of Applied Mathematics [Krakow]

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


Volume: Vol. 10 no. 1
Section: Graph and Algorithms
Published on: January 1, 2008
Imported on: March 26, 2015
Keywords: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]

1 Document citing this article

Consultation statistics

This page has been seen 368 times.
This article's PDF has been downloaded 427 times.