475 KB37 KB201420242023Prešeren, Ana Julijaletnik:1013 str.številka:2COBISSID_HOST:166247939ISSN:2385-8567URN:URN:NBN:SI:doc-4XHO3CGNslZaložba Fakultete za matematiko in fiziko Univerze v LjubljaniMatrikabondage edge setbondage numberdominantna množicadominantno številodominating setdomination numberkrepki produktkritična množica povezavpovezavno kritično številostrong productDominacija v krepkih produktih polnih grafov in poti|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}$?Dominantna množica grafa ?$G$? je podmnožica množice vozlišč ?$V(G)$?, za katero velja, da je vsako vozlišče grafa ?$G$? prisotno v tej množici ali pa je sosedno vozlišču v njej. Dominantno število grafa, označujemo ga z ?$\gamma(G)$?, je kardinalnost dominantne množice najmanjše moči. V delu poiščemo točno vrednost dominantnega števila krepkega produkta polnega grafa in poti. Njegova vrednost je neodvisna od velikosti polnega grafa in je enaka ?$\gamma(K_m \boxtimes P_n) = \lceil \frac{n}{3} \rceil$?. Kritična množica povezav grafa ?$G$? je podmnožica množice povezav ?$E(G)$?, katere odstranitev povzroči, da je dominantno število dobljenega grafa večje kot prej. Povezavno kritično število grafa je kardinalnost kritične množice povezav najmanjše moči. Označujemo ga z ?$b(G)$?, pomaga pa nam pri ocenjevanju občutljivosti povezovalnih omrežij na propad povezav. Povezavno kritično število krepkega produkta polnega grafa in poti je odvisno od velikosti polnega grafa ?$K_m$? in vrednosti ?$n$? po ?$\pmod{3}$?. Za naravni števili ?$m$? in ?$n$?, ?$m\geq 1$? in ?$n \geq 2$?, velja, da je ?$b(K_m \boxtimes P_n)=\lceil \frac{m}{2} \rceil$?, če je ?$n\equiv 0 \pmod{3}$?, ?$b(K_m \boxtimes P_n)=\lceil \frac{3m}{2} \rceil$?, če je ?$n\equiv 1 \pmod{3}$? in ?$b(K_m \boxtimes P_n)=m$?, če je ?$n\equiv 2 \pmod{3}$?TEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of Slovenia