magistrsko delo
Teja Bezgovšek (Avtor), Iztok Peterin (Mentor)

Povzetek

V magistrskem delu so obravnavane in s slikovnimi zgledi predstavljene nekatere lastnosti posplošenih grafov Sierpińskega, zgrajenih na poljubnem baznem grafu G. V prvem poglavju so povzete osnovne definicije iz teorije grafov, ki so pomembne pri razumevanju magistrskega dela. Nato so predstavljeni grafi Sierpińskega in definirani posplošeni grafi Sierpińskega. Tretje poglavje obravnava popolno kromatično število obravnavanih grafov, med drugim tudi za konkretne primere baznih grafov, in sicer graf hiše, kolo, cikel in hiperkocko. V četrtem poglavju so z zgledi podane formule za izračun števila listov, število vozliščnega pokritja in neodvisno število v posplošenih grafih Sierpińskega. V poglavju je dokazano, da sta kromatično in klično število teh grafov enaka kot v bazi. V nadaljevanju je podana zgornja meja dominacijskega števila obravnavanih grafov in tudi točno dominacijsko število teh grafov z dotičnimi lastnostmi. V zadnjem poglavju je dokazana spodnja meja krepke metrične dimenzije posplošenih grafov Sierpińskega in podana je formula za izračun te lastnosti v obravnavanih grafih, v katerih je vsako notranje vozlišče presečno vozlišče.

Ključne besede

magistrska dela;posplošeni grafi Sierpińskega;popolno kromatično število;število vozliščnega pokritja;dominacijsko število;krepka metrična dimenzija;

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.09 - Magistrsko delo
Organizacija: UM FNM - Fakulteta za naravoslovje in matematiko
Založnik: [T. Bezgovšek]
UDK: 519.17(043.2)
COBISS: 24415496 Povezava se bo odprla v novem oknu
Št. ogledov: 727
Št. prenosov: 71
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: Some properties of generalized Sierpiński graphs
Sekundarni povzetek: This master's thesis deals with certain properties of generalized Sierpiński graphs, which are based upon an arbitrary base graph G. The first chapter summarizes certain basic definitions from the theory of graphs, which are important for understanding the concepts described in this thesis. Later Sierpiński graphs and generalized Sierpiński graphs are defined. The third chapter discusses the total chromatic number of the graphs that are dealt with in this thesis, among others actual examples of base graphs, namely house graph, wheels, cycles and hypercubes. In chapter four the given examples present us certain formulas for calculating the number of leafs, the vertex cover number and the independence number of generalized Sierpiński graphs. In this chapter we also show that the chromatic and the clique number of such graphs is the same as in the base graph. In the following the upper bound of the domination number of the discussed graphs is given as well as the exact domination number in the case of special properties of the base graph. In the final chapter we present a lower bound of a strong metric dimension of generalized Sierpiński graphs and gives the formula, which is necessary to calculate these features in these graphs, in which each internal vertex is also considered to be a cut vertex.
Sekundarne ključne besede: master theses;generalized Sierpiński graphs;total chromatic number;vertex cover number;domination number;strong metric dimension;
URN: URN:SI:UM:
Vrsta dela (COBISS): Magistrsko delo/naloga
Komentar na gradivo: Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Strani: VIII, 58 f.
ID: 11008207