Vijest

NEW DOCTORAL DEGREES Domination numbers of simple polygonal chains and multiple linear hexagonal chains

Snježana Majstorović orcid.org/0000-0002-3083-0932 ; Department of Mathematics, University of Osijek, Osijek, Croatia

Sažetak

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.

This thesis is focused on distance $k$-domination and total domination on two types of graphs: simple polygonal chains (with cactus chains included) and multiple linear hexagonal chains. After determination of domination numbers of equidistant cactus chains, extremal chains regarding this graph invariant are found. Some results about edge domination are presented for hexagonal cactus chains and then compared to (vertex) domination. Some results were presented about domination ratio. For simple polygonal chains considered types of domination are also investigated.
At last, the domination numbers of multiple linear hexagonal chains were determined.

The most important part of the thesis is proof that considered dominating set has minimum cardinality among all dominating sets of considered graph. Usual procedure is to either establish that dominating set is perfect, or try to find some obvious property that every (and therefore the minimum) dominating set satisfies or do the partition of graph into smaller parts, called blocks, on which the domination number can be easily established.

Ključne riječi

Hrčak ID:

74905

URI

https://hrcak.srce.hr/74905

Datum izdavanja:

21.12.2011.

Posjeta: 1.402 *