Groupe d’études et de recherche en analyse des décisions

Types of domination on m-ary chain cacti

Snjezana Majstorovic

Domination is an area in graph theory with an extensive research activity, together with its numerous generalizations and modifications, motivated by various applications and problems. The most interesting part of this area is the multitude of types of domination.

In general, a dominating set of a graph is a set \(D\) such that every vertex of a graph is either in \(D\) or is adjacent to some vertex in \(D\). Domination number is the cardinality of the smallest dominating set \(D\).

The problem to determine the domination number of graph is NP-hard even when restricted to some simple graph structures. However, there are certain graph structures for which domination numbers can be determined by using some well-known mathematical tools like mathematical induction or partition of graph into small parts, mutually isomorphic subgraphs, for which domination number can be easily established.

The goal of this seminar is to present results about several types of domination on a \(m\)-ary chain cacti: distance \(k\)-domination and total domination. The minimum dominating sets were determined together with the corresponding results on domination numbers.