Dominacija v krepkih produktih polnih grafov in poti - Prešeren, Ana Julija (Matrika, 2023)
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 ?$γ(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 ?$γ(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≥ 1$? and ?$n ≥ 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}$?.
Keywords: bondage edge set; bondage number; dominantna množica; dominantno število; dominating set; domination number; krepki produkt; kritična množica povezav; povezavno kritično število; strong product