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

Kišek, Anja (author), 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.

• Language: Slovenian
• Keywords: kograf, kodrevo, varnostnodominantno število, dominantno število, popoln graf, linearen algoritem
• Work type: Master's thesis/paper
• Typology: 2.09 - Master's Thesis
• Organization: FMF - Faculty of Mathematics and Physics
• Year: 2021
• PID: 20.500.12556/RUL-126403
• UDC: 519.1
• COBISS.SI-ID: 60413955
• Publication date in RUL: 21.04.2021

Secondary language

• Language: English
• Title: Characterisation of cographs and two algorithms for computation of secure domination number of a cograph

Abstract

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.

• Keywords: cograph, cotree, security domination number, domination number, perfect graph, linear algorithm