Dominacija v krepkih produktih polnih grafov in potiPrešeren, Ana Julija (Avtor) Klavžar, Sandi (Mentor) dominantna množicadominantno številokrepki produktkritična množica povezavpovezavno kritično številoDominantna 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}$.20232023-06-10 08:15:01Delo diplomskega seminarja/zaključno seminarsko delo/naloga146749UDK: 519.17VisID: 131233COBISS_ID: 155431939sl