20.500.12556/DKUM-59473 K-geodominantne množice v grafih in sorodni koncepti K-geodominating sets in graphs and related concepts 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. A set S of vertices of a graph Г is a geodominating set if every vertex of Г lies in at least one interval between the vertices of S. For an integer k≥1, a vertex v is k-geodominated by a pair x,y∈V(Г) if v lies on a shortest path of length k between vertices x and y. A subset S⊆V(Г) is a k-geodominating set if each vertex v∈V(Г) S is k-geodominated by some pair of vertices of S. An independent set is a set of vertices in a graph, no two of which are adjacent. An independent set of in Г that is a (k-)geodominating set of Г is called an independent (k-)geodominating set of Г. A dominating set for a graph Г is a subset D⊆V(Г) such that every vertex not in D is adjacent to at least one member of D. The graduation thesis investigates relationships between geodominating, k-geodominating sets, dominating sets and independent sets in arbitrary graphs. Some properties of geodominating sets in line graphs and Cartesian products are given. Also, independent geodominating sets and independent k-geodominating sets are studied. geodominantna množica k-geodominantna množica totalna k-geodominantna množica neodvisna geodominantna množica neodvisna k-geodominantna množica. geodominating set k-geodominating set total k-geodominating set independent geodominating set independent k-geodominating set. true true false [K. Kotnik] Slovenski jezik Angleški jezik Diplomsko delo 2016-05-18 13:14:53 2016-09-08 14:11:30 2022-06-20 03:07:05 2019-07-11 11:14:55 2016 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17(043.2) 22503176 URN:SI:UM:DK:RHZOKUWN UN_Kotnik_Katja_2016.pdf UN_Kotnik_Katja_2016.pdf 1 03FF0141FBC2FA2D610AE442C06F9C44 4163409acd6ecb95fc51e8dbefd9881e918dbc786cdfbc3fd91895c95415c952 7a2c6d0b-7c0c-11eb-bb7a-00155d0001ca https://dk.um.si/Dokument.php?lang=slv&id=91872 Fakulteta za naravoslovje in matematiko 0 0 0