20.500.12556/RUL-146749 Dominacija v krepkih produktih polnih grafov in poti delo diplomskega seminarja Domination in the strong product of a complete graph with a path 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}$. 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 dominantno število krepki produkt kritična množica povezav povezavno kritično število dominating set domination number strong product bondage edge set bondage number true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2023-06-10 08:15:01 2023-06-10 08:15:06 2024-05-29 10:48:22 0000-00-00 00:00:00 2023 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 131233 155431939 7732.pdf 7732.pdf 1 1751F5CD8807C34603C72073548C8E29 bb77145d163b5ce06d7b439ee094a1ca972ab629bb6799f5b7f6ccbc7836d75b cf01fac9-0755-11ee-a314-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=170028 Fakulteta za matematiko in fiziko 0 0 0