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
Datum izdavanja:
21.12.2011.
Posjeta: 1.321 *