diplomsko delo
Nika Čelan (Author), Sandi Klavžar (Mentor)

Abstract

V nalogi je najprej predstavljena terminologija in teoretične osnove potrebne za razumevanje pojmov varnosti, dominacije in varnostne dominacije v grafih. V drugem delu diplomskega dela, bomo definirali grafe Sierpińskega. Povedali bomo, kako so nastali in kakšne so njihove lastnosti. Za lažje razumevanje bomo tudi narisali nekaj manjših primerov grafov Sierpińskega. Glavna tema naloge so rezultati iz članka Security in Sierpiński graphs. Razložili bomo dokaz izreka za varnostno število grafov Sierpińskega in dokazali potrebne leme. V nalogi bomo iskali tudi varnostno dominacijsko število grafov Sierpińskega. Ta problem bomo razdelili na dva dela in sicer za grafe S_p^n s sodim p in za grafe S_p^n z lihim p. Za sode bomo poiskali točno formulo za varnostno dominacijsko število, za lihe pa bomo podali le zgornjo mejo, saj je iskanje točne formule še odprt problem.

Keywords

varnost v grafih;varnostno število;varnostno dominacijsko število;graf Sierpińskega;interdisciplinarni študij;univerzitetni študij;diplomske naloge;

Data

Language: Slovenian
Year of publishing:
Typology: 2.11 - Undergraduate Thesis
Organization: UL FRI - Faculty of Computer and Information Science
Publisher: [N. Čelan]
UDC: 519.17(043.2)
COBISS: 169223427 Link will open in a new window
Views: 74
Downloads: 12
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: English
Secondary title: Security number of Sierpiński graphs
Secondary abstract: The thesis first introduces the terminology and the theoretical basics necessary to understand the concepts of security, domination, and secure domination in graphs. In the second part of the thesis, graphs of Sierpiński will be defined. It will be explained how they were created and what their characteristics are. To make it more understandable, some small examples of Sierpiński graphs will also be drawn. The proof of the theorem for the security number of Sierpiński graphs will be explained and the necessary lemmas will be proved. We will also look for the secure domination number of Sierpiński graphs. This problem will be divided into two parts, namely for the graphs S_p^n with even p and for graphs S_p^n with odd p. For even p we will find the exact formula for the secure domination number, for odd p we will only give the upper bound since finding the exact formula is still an open problem.
Secondary keywords: security in graphs;security number;secure domination number;Sierpiński graph;computer science;computer science and mathematics;interdisciplinary studies;diploma;Teorija grafov;Matematika;Računalništvo;Univerzitetna in visokošolska dela;
Type (COBISS): Bachelor thesis/paper
Study programme: 1000407
Embargo end date (OpenAIRE): 1970-01-01
Thesis comment: Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages: 44 str.
ID: 19945586