UJ world-leading researcher on graph theory receives second NRF A-rating

Date: Aug 31, 2015 | News

Prof Michael Henning received his second A-rating by the National Research Foundation (NRF) at a prestigious NRF award ceremony on Thursday, 27 August in Durban. Prof Henning is a research professor at the Department of Pure and Applied Mathematics at the University of Johannesburg (UJ).

Prof Henning’s research uses graph theory, which is used in every GPS navigation system to find an optimal route to drive on city streets between two points.

Graph theory is the study of graphs, which are mathematical structures used to model a collection of objects (called vertices), some of which are related.

For example, a road network in a city can be modelled as a graph in which the street intersections are represented by vertices.

There are very efficient graph theory algorithms to find the shortest distance between two vertices in such a graph that models a road network, says Prof Henning.

The National Research Foundation (NRF) A-rating is awarded to “researchers who are unequivocally recognised by their peers as leading international scholars in their field for the high quality and impact of their recent research outputs.”

Prof Henning says that the Swiss mathematician Leonhard Euler’s famous pursuit of a solution to the celebrated Königsberg (now called, Kaliningrad) Bridges Problem in 1735 is considered by many to be the beginning of the field of graph theory. “Graph theory is a relatively young discipline of mathematics with the first textbook on the subject, due to Dénes König, only appearing in 1936.”

Graph theory has proven to be particularly useful to a large number of rather diverse fields. For example, graphs can be used to count the alkane hydrocarbons in chemistry, or to design the layout of electronic circuit boards, or even to improve the planning of municipal services. “If you want to optimise the route for rubbish collection that is done using graph theory,” continues Prof Henning.

In contrast, hypergraph theory is more structured and general than graph theory. It is a very useful branch of mathematics to solve optimisation problems such as scheduling problems and location problems. For example, hypergraph theory can be used to construct a teaching timetable for a university without any clashes in the schedules of the lecturers, students or venues.

“Total domination in graphs can be translated to the problem of finding transversals in hypergraphs. Indeed, the total domination number of a graph is precisely the transversal number of its open neighbourhood hypergraph. Using this beautiful interplay between total dominating sets in graphs and transversals in hypergraphs, several results on total domination in graphs can be obtained that appear very difficult to obtain using purely graph theoretic techniques. The main strength of this approach of using transversals in hypergraphs is that in the induction steps we can move to hypergraphs which are not open neighbourhood hypergraphs of any graph, thereby giving us much more flexibility,” says Henning.

UJ currently has six A-rated researchers across its Science, Engineering, Health Sciences and Humanities faculties.

Prof Henning has made significant contributions to several topics in graph theory and hypergraph theory. His favourite topic is in the area of domination theory in graphs, where his fundamental contributions have established him as a world-leader in the field.

Over the last decade, Prof Henning and Prof Anders Yeo (currently at Singapore University of Technology and Design) have combined forces and focused their research on the interplay of total domination in graphs and transversals in hypergraphs.

Several of their results employ techniques from structural aspects of graph and hypergraph theory, including colourings; matchings; independence and domination; and directed graphs. They also extensively use combinatorics and probability to obtain certain results. Henning and Yeo recently co-authored a book in 2013 entitled Total domination in graphs (Monographs in Springer Mathematics).

Prof Henning is a prolific researcher having published over 365 papers to date in international mathematics journals.

He collaborates extensively and has co-authors from several countries, including the USA, England, Canada, France, Israel, Germany, Poland, Mexico, Slovenia, Singapore, Denmark, Hungary, India, and China. His current main collaborators are Prof Wayne Goddard (USA); Prof Teresa Haynes (USA); Prof Douglas Rall (USA); Prof Dr Dieter Rautenbach (Germany); Prof Paul Dorbec (France); Prof Odile Favaron (France); Prof Anders Yeo (Singapore); Prof Sandi Klavzar (Slovenia); Dr Christian Loewenstein (Germany); and Prof Zsolt Tuza (Hungary).

Of his early papers, one which he treasures, is a paper published in 1993 with Prof Paul Erdős, a Hungarian mathematician. Erdős was one of the most prolific publishers of papers in mathematical history, comparable only with Leonhard Euler.

Google Scholar Profile for Prof Henning.

Prof Henning

Latest News

| View All News

UJ confers honorary degree on British sociologist, Prof Michael Burawoy

The University of Johannesburg (UJ) is awarding an honorary doctorate


Siphosethu rises above health issues to make her mark in…

Environmental Health graduate Siphosethu Cele has always made it her


Reflections on Writing on Case Study Research

By Seriane Morapeli & Elmon Motloutsi University of Johannesburg Case


Fourth Industrial Revolution – Beyond Competencies

By Prof Sonja Verwey University of Johannesburg Introduction The Fourth


Fourth Industrial Revolution – Future-Fit Graduates

By Prof Sonja Verwey University of Johannesburg Introduction In this