Hedetniemijeva domneva in retrakti produktivnih grafov
diplomsko delo
Abstract
Osrednji del diplomskega dela predstavljata Hedetniemijeva domneva in retrakti grafov. V delu je obravnavan pojem homomorfizmov med grafi, to je preslikava med grafi, ki ohranja povezave, ter kombinatorična struktura direktnih grafovskih produktov. Uvodno poglavje je namenjeno pregledu osnovnih pojmov, ki izhajajo s področja teorije grafov in teorije grup. Nato so bolj podrobno obravnavane preslikave med grafi, kromatično število grafa, retrakt in jedro grafa. V nadaljevanju je predstavljena Hedetniemijeva domneva in njene ekvivalentne trditve. Predstavljena je trditev, ki povezuje retrakt produktnega grafa z osrednjo domnevo.
Keywords
diplomska dela;Hedetniemijeva domneva;produktni grafi;retrakti grafov;jedro grafov;homomorfizem grafov;kromatična števila;
Data
| Language: | Slovenian |
|---|---|
| Year of publishing: | 2016 |
| Typology: | 2.11 - Undergraduate Thesis |
| Organization: | UM FNM - Faculty of Natural Sciences and Mathematics |
| Publisher: | [A. Bezjak] |
| UDC: | 519.17(043.2) |
| COBISS: |
22507784
|
| Views: | 1131 |
| Downloads: | 69 |
| Average score: | 0 (0 votes) |
| Metadata: |
|
Other data
| Secondary language: | English |
|---|---|
| Secondary title: | Hedetniemi's conjecture and the retracts of a product of graphs |
| Secondary abstract: | The central part of the thesis focusses on Hedetniemi's Conjecture and the Retracts of a Product of Graphs. The thesis discusses the concept of homomorphism's among graphs, this mapping preserves the edges between the graphs. Combinatorial structure of the direct product is also discussed. The introductory chapter is devoted to a basic review of the theory of graphs, as well as group theory. More detail on mapping between graphs, chromatic number, retract, and core graph is discussed in subsequent chapters. The thesis continues with the introduction of Hedetniemi's conjecture and its equivalent statements. It also presents an theorem that connects the retracts of a product graphs with the central conjectuere. |
| Secondary keywords: | theses;Hedetniemi's conjecture;product of graphs;rectracts of graphs;core graphs;homomorphism;cromatic numbers;Univerzitetna in visokošolska dela; |
| URN: | URN:SI:UM: |
| Type (COBISS): | Undergraduate thesis |
| Thesis comment: | Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo |
| Pages: | IX, 44 f. |
| ID: | 9149859 |
Recommended works:
Hedetniemijeva domneva in retrakti produktivnih grafov
2016,
diplomsko delo
Counterexamples to Orlin's conjecture on equistable graphs
2014,
Raziskovalni matematični seminar, Univerza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologije, Koper, 24. 3. 2014
The k-independence number of direct products of graphs and Hedetniemi's conjecture
2011,
no subtitle data available
Counterexamples to three conjectures on equistable graphs
2015,
no subtitle data available
Domination game
2009,
no subtitle data available