Izbrane teme sodobne fizike in matematike
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 γ(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 γ(Km ⊠Pn) = ⌈ n 3 ⌉. 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 Km in vrednosti n po (mod 3). Za naravni števili m in n, m ≥ 1 in n ≥ 2, velja, da je b(Km ⊠ Pn) = ⌈ m 2 ⌉, če je n ≡ 0 (mod 3), b(Km ⊠ Pn) = ⌈ 3m 2 ⌉, če je n ≡ 1 (mod 3) in b(Km ⊠ Pn) = m, če je n ≡ 2 (mod 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 γ(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 γ(Km ⊠ Pn) = ⌈ n 3 ⌉. 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 (mod 3). For integers m and n, where m ≥ 1 and n ≥ 2, b(Km ⊠ Pn) = ⌈ m 2 ⌉ if n ≡ 0 (mod 3), b(Km ⊠ Pn) = ⌈ 3m 2 ⌉ if n ≡ 1 (mod 3) and b(Km ⊠ Pn) = m if n ≡ 2 (mod 3).