Število kromatične stabilnosti povezav

magistrsko delo

Tjaša Kos (Avtor), Tanja Gologranc (Mentor)

Povzetek

V magistrskem delu predstavimo število kromatične stabilnosti povezav grafa ▫$G$▫. Najprej definiramo osnovne pojme teorije grafov in dokažemo nekaj lastnosti števila kromatične stabilnosti povezav. Opišemo grafe Mycielskega, njihovo konstrukcijo ter dokažemo, da je kromatično število grafa Mycielskega ▫$M(G)$▫ za ena večje od kromatičnega števila grafa ▫$G$▫. Nato se osredotočimo na število kromatične stabilnosti povezav posebnih družin grafov. Raziskujemo disjunktno unijo grafov, kartezični produkt, spoj grafov ter posebne družin grafov, ki jih dobimo s spojem nekaterih družin grafov. V nadaljevanju opišemo meje števila kromatične stabilnosti povezav. Dokažemo več spodnjih in zgornjih mej za ▫$es_{\chi}(G)$▫. Osredotočimo se tudi na rezultate tipa Nordhaus-Gaddum in dokažemo zgornjo mejo za vsoto števila kromatične stabilnosti povezav grafa ▫$G$▫ in njegovega komplementa ▫$\overline{G}$▫. Nazadnje raziskujemo grafe z ▫$es_{\chi}(G)=1$▫. Dokažemo, da je ▫$es_{\chi}(G)=1$▫ natanko tedaj, ko je vezano kromatično število enako ▫$1$▫. Še več, predstavimo več potrebnih pogojev za graf ▫$G$▫ z ▫$es_{\chi}(G)=1$▫.

Ključne besede

magistrska dela;število kromatične stabilnosti povezav;kromatično število;dvodelni grafi;kartezični produkt grafov;gradi Mycielskega;neenakost tipa Nordhaus-Gaddum;vezano kromatično število;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2020
Tipologija:	2.09 - Magistrsko delo
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
Založnik:	[T. Kos]
UDK:	519.17(043.2)
COBISS:	34653187
Št. ogledov:	349
Št. prenosov:	42
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	ǂThe ǂchromatic edge stability number of a graph
Sekundarni povzetek:	The master's thesis presents the chromatic edge stability number of a graph ▫$G$▫. Firstly the basic concepts of graph theory and the chromatic edge stability number are presented. Described are Mycielski graphs, their construction and the proof that chromatic number of Mycielski graph ▫$M(G)$▫ is greater by one than the chromatic number of the graph ▫$G$▫. Then we focus on the chromatic edge stability number for specific graph classes. We investigate $es_{\chi}(G)$ for a disjoint union of graphs, a Cartesian product, join of two graphs and families of graphs, which can be described as the join of two graphs. Next, upper and lower bounds for the chromatic edge stability number are presented. We prove several lower and upper bounds for ▫$es_{\chi}(G)$▫. We also focus on the Nordhaus-Gaddum type results and prove the upper bound for the sum of the chromatic edge stability number of graph ▫$G$▫ and its complement ▫$\overline{G}$▫. Finally, we explore graphs with ▫$es_{\chi}(G)=1$▫. We prove that ▫$es_{\chi}(G)=1$▫ if and only if the chromatic bondage number of ▫$G$▫ is ▫$1$▫. Moreover, we present several sufficient conditions for the graph ▫$G$▫ with ▫$es_{\chi}(G)=1$▫.
Sekundarne ključne besede:	master theses;the chromatic edge stability number;chromatic number;bipartite graphs;Cartesian product of graphs;Mycielski graphs;Nordhaus-Gaddum type results;the chromatic bondage number;
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, 46 f.
ID:	11919838