K-geodominantne množice v grafih in sorodni konceptiKotnik, Katja (Avtor) Tepeh, Aleksandra (Mentor) geodominantna množicak-geodominantna množicatotalna k-geodominantna množicaneodvisna geodominantna množicaneodvisna k-geodominantna množica.Množica vozlišč S grafa Г je geodominantna množica, če poljubno vozlišče grafa Г leži na vsaj enem intervalu med vozliščema iz S. Za naravno število k je vozlišče v k-geodominirano z vozliščema x,y∈V(Г), če v leži na neki najkrajši poti dolžine k med vozliščema x in y. Podmnožica S⊆V(Г) je k-geodominantna množica, če je vsako vozlišče v∈V(Г) S k-geodominirano z nekim parom vozlišč iz S. Množica vozlišč v grafu je neodvisna, če nobeni dve vozlišči iz te množice nista povezani. Neodvisna množica, ki je (k"-" )geodominantna, se imenuje neodvisna (k"-" )geodominantna množica grafa Г. Dominantna množica grafa Г je taka podmnožica D⊆V(Г), da je vsako vozlišče, ki ni v D, sosedno z vsaj enim vozliščem iz D. Diplomsko delo obravnava zveze med geodominantnimi, k-geodominantnimi, dominantnimi in neodvisnimi množicami v poljubnih grafih. Podane so nekatere lastnosti geodominantnih množic v povezavnih grafih in kartezičnih produktih. Prav tako so obravnavane lastnosti neodvisnih geodominantnih in neodvisnih k-geodominantnih množic.[K. Kotnik]20162016-05-18 13:14:53Diplomsko delo59473sl