| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Show document

Title:Število kromatične stabilnosti povezav
Authors:Kos, Tjaša (Author)
Dravec, Tanja (Mentor) More about this mentor... New window
Files:.pdf MAG_Kos_Tjasa_2020.pdf (2,21 MB)
MD5: F87239B2A8131F776292A0B69D81CD29
 
Language:Slovenian
Work type:Master's thesis/paper (mb22)
Typology:2.09 - Master's Thesis
Organization:FNM - Faculty of Natural Sciences and Mathematics
Abstract: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$.
Keywords:število kromatične stabilnosti povezav, kromatično število, dvodelni grafi, kartezični produkt grafov, grafi Mycielskega, neenakost tipa Nordhaus-Gaddum, vezano kromatično število
Year of publishing:2020
Publisher:[T. Kos]
Source:Maribor
UDC:519.17(043.2)
COBISS_ID:34653187 New window
NUK URN:URN:SI:UM:DK:LNEI1KIA
Views:136
Downloads:15
Metadata:XML RDF-CHPDL DC-XML DC-RDF
Categories:FNM
:
  
Average score:(0 votes)
Your score:Voting is allowed only for logged in users.
Share:AddThis
AddThis uses cookies that require your consent. Edit consent...

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Licences

License:CC BY-NC-ND 4.0, Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
Link:http://creativecommons.org/licenses/by-nc-nd/4.0/
Description:The most restrictive Creative Commons license. This only allows people to download and share the work for no commercial gain and for no other purposes.
Licensing start date:27.07.2020

Secondary language

Language:English
Title:The chromatic edge stability number of a graph
Abstract: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$.
Keywords:the chromatic edge stability number, chromatic number, bipartite graphs, Cartesian product of graphs, Mycielski graphs, Nordhaus-Gaddum type results, the chromatic bondage number


Comments

Leave comment

You have to log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica