Karakterizacije kografov in algoritma za izračun varnostne dominacije na kografih : magistrsko delo

Kišek, Anja (avtor), Klavžar, Sandi (mentor)

V delu obravnavamo kografe, njihovo reprezentacijo s kodrevesi in karakterizacijo kografov. Uvrstimo jih v družino popolnih grafov in raziščemo problem barvanja kografov. Poleg algoritma za barvanje navedemo nekaj algoritmov, ki zaradi strukture kodrevesa delujejo v linearnem času, med njimi dominacijo in varnostno dominacijo. Slednjo definiramo in raziščemo njene lastnosti. Obravnavamo dva neodvisna algoritma za iskanje varnostnodominantnega števila na kografih in argumentiramo njuno linearnost.

• Jezik: Slovenski jezik
• Ključne besede: kograf, kodrevo, varnostnodominantno število, dominantno število, popoln graf, linearen algoritem
• Vrsta gradiva: Magistrsko delo/naloga
• Tipologija: 2.09 - Magistrsko delo
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Leto izida: 2021
• PID: 20.500.12556/RUL-126403
• UDK: 519.1
• COBISS.SI-ID: 60413955
• Datum objave v RUL: 21.04.2021

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Characterisation of cographs and two algorithms for computation of secure domination number of a cograph

Izvleček

This work studies cographs, their representation with cotrees and their different characterisations. By observing their colorings, cographs are proved to be a special case of perfect graphs. In addition, a few linear algorithms that exploit the structure of cotrees are presented. Security domination of a graph is introduced and some properties, crucial for its computation are presented. Two independent algorithms for security domination number of cographs are studied and their linearity is argumented.

• Ključne besede: cograph, cotree, security domination number, domination number, perfect graph, linear algorithm