Dominacija v krepkih produktih polnih grafov in poti

slovenian

2023

volume 10, issue 2

bondage edge set   bondage number   dominating set   domination number   strong product

Narodna in univerzitetna knjižnica
(Obvezni izvod spletne publikacije)

A dominating set of a graph ?$G$? is a subset of ?$V(G)$? with the property, that every vertex of graph ?$G$? is either in this set or is adjacent to the vertex in it. The domination number ?$\gamma(G)$? of a graph ?$G$? is the cardinality of a smallest dominating set. In this thesis we find the exact value of the domination number of the strong product of a complete graph with a path. It is not dependent on the order of the complete graph and is equal to ?$\gamma(K_m \boxtimes P_n) = \lceil \frac{n}{3} \rceil$?. A bondage edge set of a graph ?$G$? is a subset of ?$E(G)$?, whose removal from ?$G$? results in a graph with the domination number greater than that of ?$G$?. The bondage number ?$b(G)$? is the cardinality of a smallest bondage edge set. It is a parameter to measure the vulnerability of a communication network under link failure. The bondage number of the strong product of a complete graph with a path depends on the order of the complete graph and the value of ?$n \pmod{3}$?. For integers ?$m$? and ?$n$?, where ?$m\geq 1$? and ?$n \geq 2$?, ?$b(K_m \boxtimes P_n)=\lceil \frac{m}{2} \rceil$? if ?$n\equiv 0 \pmod{3}$?, ?$b(K_m \boxtimes P_n)=\lceil \frac{3m}{2} \rceil$? if ?$n\equiv 1 \pmod{3}$? and ?$b(K_m \boxtimes P_n)=m$? if ?$n\equiv 2 \pmod{3}$?.

13.02.2025