Nekatere posplošitve grafov Sierpińskega

diplomsko delo

Andreja Šereg (Avtor), Marko Jakovac (Mentor)

Povzetek

V diplomskem delu so predstavljeni grafi Sierpińskijevega tipa, in sicer grafi Sierpińskega S(n, k), grafi trikotnikov Sierpińskega S_n, regularni grafi Sierpińskega S^+(n, k) in S^++(n, k) in posplošeni grafi trikotnikov Sierpińskega S[n, k]. Prikazane so natančne risbe grafov S(n, k), S^+(n, k) in S^++(n, k). Za S^+(n, k) in S^++(n, k) je dokazano, da so te risbe optimalne. Določeno je število po povezavah disjunktnih Hamiltonovih poti in Hamiltonovih ciklov v grafih S(n, k), S^+(n, k) in S^++(n, k). Dokazano je, da so grafi S[n, k] Hamiltonovi. Raziskana je vozliščna linearna pogozdenost grafov S(n, k), S^+(n, k), S^++(n, k) in S[n, k]. Podano je še {P_r}-prosto kromatično število grafov S_n, S(n, k), S^+(n, k) in S^++(n, k), za r % {3, 4}.

Ključne besede

matematika;grafi Sierpińskega;grafi trikotnikov Sierpińskega;prekrižno število;hamiltonskost;vozliščna linearna pogozdenost;diplomska dela;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2013
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
Založnik:	[A. Šereg]
UDK:	51(043.2)
COBISS:	20061448
Št. ogledov:	1341
Št. prenosov:	104
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Some generalizations of Sierpiński graphs
Sekundarni povzetek:	In this graduation thesis Sierpiński-like graphs, namely Sierpiński graphs S(n, k), Sierpiński gasket graphs S_n, regular Sierpiński graphs S^+(n, k) and S^++(n, k) and generalized Sierpiński gasket graphs S[n, k] are presented. Explicit drawings of graphs S(n, k), S^+(n, k) and S^++(n, k) are shown and proved to be optimal for S^+(n, k) and S^++(n, k). The numbers of edge disjoint Hamiltonian paths and Hamiltonian cycles in S(n, k), S^+(n, k) and S^++(n, k) are determined. Graphs S[n, k] are proven to be Hamiltonian. Vertex linear arboricity of S(n, k), S^+(n, k), S^++(n, k) and S[n, k] is studied. {Pr}-free cromatic number of S_n, S(n, k), S^+(n, k) and S^++(n, k) for r % {3, 4} is given.
Sekundarne ključne besede:	Sierpiński graph;Sierpiński gasket graph;regular Sierpiński graph;generalized Sierpiński gasket graph;crossing number;Hamiltonicity;path t-coloring;vertex linear arboricity;{P_r}-free chromatic number;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Diplomsko delo
Komentar na gradivo:	Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Strani:	IX, 63 f.
ID:	8726882