Skip to Main content Skip to Navigation
Journal articles

Recurrence among trees with most numerous efficient dominating sets

Abstract : 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-00972308
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Thursday, April 3, 2014 - 4:07:46 PM
Last modification on : Tuesday, December 17, 2019 - 5:48:02 PM
Long-term archiving on: : Thursday, July 3, 2014 - 4:30:51 PM

File

610-3174-1-PB.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Dorota Bród, Zdzis\law Skupień. Recurrence among trees with most numerous efficient dominating sets. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2008, Vol. 10 no. 1 (1), pp.43--55. ⟨10.46298/dmtcs.445⟩. ⟨hal-00972308⟩

Share

Metrics

Record views

59

Files downloads

562