20.500.12556/DKUM-40050 Vozliščno pokritje k-poti v grafih The k-path vertex cover of graphs Diplomsko delo obravnava vozliščno pokritje k-poti v grafih. Na začetku so predstavljeni osnovni pojmi teorije grafov, ki so potrebni za razumevanje nadaljne snovi. V nalogo so vključeni pojmi NP-polnost, regularni grafi in drevesa. Konec pa vključuje vozliščna pokritja k-poti za nekatere grafovske produkte. Za velikost najmanjšega vozliščnega pokritja glede na stopnjo vozlišča bodo določene zgornje in spodnje meje grafa. Izboljšani bosta zgornja in spodnja ocena za najmanjše možno število vozlišč v pokritju k-poti pri kartezičnem, krepkem in leksikografskem produktu. The diploma thesis deals with the k-path vertex cover of graphs. In the beginning, we will present the basic concepts of graph theory which are essential for further understanding of the subject. There are concepts of NP-completeness, regular graphs, and trees involved in the thesis. In the conclusion the k-path vertex cover of some graph products is determined. For the minimum k-path vertex cover we will determine some lower and upper bounds of graphs in respect to its degree. Lower and upper bounds for the minimum k-path vertex cover of the Cartesian product, the strong product, and the lexicographic product will also be improved. Vozliščno pokritje NP-polnost regularni graf kartezični produkt krepki produkt leksikografski produkt. Vertex cover NP-completeness regular graphs the Cartesian product the strong product the lexicographic product. true true false [I. Jesih] Slovenski jezik Angleški jezik Diplomsko delo 2013-04-02 09:22:49 2013-04-22 12:52:55 2022-05-12 23:23:49 2021-04-23 03:14:20 2013 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17(043.2) 19825928 URN:SI:UM:DK:UEYOMKRE UNI_Jesih_Igor_2013.pdf UNI_Jesih_Igor_2013.pdf 1 A0AA9A90E9B186A1434926B3C19A80A6 81d9f419102ef23bf632f4bfcd36113ab50d537ae2617dfccb0a077c64a58b85 438b4080-7c09-11eb-bb7a-00155d0001ca 20.500.12556/dkum/0a66dd35-34ae-435b-9301-2395b3af7b3f https://dk.um.si/Dokument.php?lang=slv&id=54554 Fakulteta za naravoslovje in matematiko 0 0 0