Dominacija v krepkih produktih polnih grafov in poti

slovenski

2023

letnik 10, številka 2

dominantna množica   dominantno število   krepki produkt   kritična množica povezav   povezavno kritično število

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

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}$?.

13.02.2025