Research is at the core of Durham University. It shapes and inspires the disciplinary structure of our departments, several of which lead the UK - and even the world - in their fields. Research leads the content and development of our teaching at undergraduate and postgraduate levels, and creates new cross-disciplinary programmes through our centres and institutes. In partnership with policy-makers, industry, healthcare and education, Durham's cross-disciplinary and cross-cultural research shapes local, national and international agendas.
Links to recent research highlights and to the Research Office and other units and schemes that support our research can be found on this page.
Forthcoming research seminars
Minimal Dominating Sets in Graphs: Enumeration, Combinatorial Bounds and Graph Classes
In 2008 Fomin, Grandoni, Pyatkin and Stepanov provided an exact exponential time algorithm to enumerate all minimal dominating sets of a graph. Its main consequence was the first non trivial upper bound on the number of minimal dominating sets; the maximum number of minimal dominating sets that a graph on n vertices can have is at most 1.7159^n. This upper bound might not be tight, since no examples of graphs with 1.5705^n or more minimal dominating sets are known.
This talk considers exact exponential algorithms to enumerate minimal dominating sets when the input graphs are restricted to certain graph classes, among them chordal graphs, cographs and chain graphs. The following types of results exploiting the structure of the particular graph classes are presented: (i) enumeration algorithms based on branching algorithms and their analysis via upper bounding the number of leaves in search trees, (ii) upper bounds on the maximum number of minimal dominating sets in n-vertex graphs obtained via branching algorithms or combinatorial proofs, (iii) lower bounds on the maximum number of minimal dominating sets. In some cases, we provide examples of graphs whose number of minimal dominating sets exactly matches the proved upper bound for that class, thereby showing that these bounds are tight.
Contact email@example.com for more information about this event.
Visit Durham's brand new research microsite - Breakthrough - for examples of our latest research, outstanding achievements and research grants.