BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: A tree with n vertices has at most 95 n/13 minimal dominating
sets. The growth constant λ= 13 √95≈1.4194908 is best possible. It is obta
ined in a semi-automatic way as a kind of " dominant eigenvalue " of a bili
near operation on sextuples that is derived from the dynamic-programming re
cursion for computing the number of minimal dominating sets of a tree. The
core of the method tries to enclose a set of sextuples in a six-dimensional
geometric body with certain properties\, which depend on some putative val
ue of λ. This technique is generalizable to other counting problems\, and i
t raises interesting questions about the "growth" of a general bilinear ope
ration. We also derive an output-sensitive algorithm for listing all mini
mal dominating sets with linear set-up time and linear delay between succes
sive solutions.
DTSTAMP:20220119T183600
DTSTART:20220124T141500
CLASS:PUBLIC
LOCATION:Online via Zoom
SEQUENCE:0
SUMMARY:Günter Rote (Freie Universität Berlin): The maximum number of minim
al dominating sets in a tree
UID:107920019@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20220124-L-Rote.html
END:VEVENT
END:VCALENDAR