Please use this identifier to cite or link to this item: https://hdl.handle.net/10593/445
Title: Metody Algorytmiczne w Badaniach Siły Nieregularności Grafów
Other Titles: Algorithmic Methods for the Irregularity Strength of Graphs
Authors: Kalkowski, Maciej
Advisor: Karoński, Michał. Promotor
Keywords: grafy
graphs
algorytmy
algorithms
siła nieregularności
irregularity strength
kolorowanie
coloring
Issue Date: 11-Jun-2010
Abstract: Celem rozprawy jest przedstawienie nowych metod rozwiązywania problemów globalnej i lokalnej siły nieregularności grafów. Powyższe dwa zagadnienia są rozpatrzone zarówno dla grafów ważonych, jak i totalnie ważonych. Wszystkie przedstawione metody i dowody mają charakter algorytmów wyznaczających wartości funkcji ważących. Rozdział drugi składa się z dwóch części i dotyczy lokalnego rozróżniania wierzchołków. W pierwszej, zagadnienie omówione jest dla totalnego ważenia. Wprowadzone są dwa twierdzenia, dowodzące, że istnieją lokalnie nieregularne 5-totalne-ważenie oraz 3-totalne-ważenie. W drugiej części rozdziału rozważony jest problem rozróżniania wierzchołków dla ważenia krawędzi nawiązujący do hipotezy 1-2-3. Wprowadzone są trzy nowe metody rozwiązania problemu, które wykazują, że możliwe są konstrukcje lokalnie nieregularnych 10-ważenia, 6-ważenia i 5-ważenia grafu. Rozdział trzeci dotyczy globalnego rozróżniania wierzchołków i również składa się z dwóch części. W pierwszej, zagadnienie rozpatrzone jest dla ważenia krawędzi grafu. Opisana jest metoda konstrukcji globalnie nieregularnego 6 ⌈n/δ⌉ -ważenia grafu. W drugiej części rozdziału omówione jest globalne rozróżnianie wierzchołków dla totalnego ważenia grafów. Wykazana jest konstrukcja globalnie nieregularnego (3⌈n/δ ⌉+1)-totalnego-ważenia. W ostatnim rozdziale przedstawione są pokrewne problemy rozróżniania wierzchołków.
The thesis deals with new methods for solving the local and global irregularity strength problems. Both issues are discussed considering weightings and total weightings of a graph. All presented methods and proofs have an algorithmic construction, which assigns weights to a graph. The second chapter covers the problem of distinguishing connected vertices. First part considers total weightings. Two new theorems are presented, proving that there exist locally irregular 5-total-weighting and 3-total-weighting. Second part investigates weightings of a graph. Three new results are discussed, showing that there exist 10-weighting, 6-weihgting and 5-weighting, all locally irregular. The third chapter covers the problem of distinguishing all vertices of a graph. First part considers weightings of a graph. A new result is presented, which shows that there exist vertex distinguishing 6 ⌈n/δ⌉-weighting. Second part investigates total-weightings of a graph. A new construction of vertex distinguishing (3⌈n/δ ⌉+1)-total-weighting is proved. The last chapter considers other related graph coloring problems.
Description: Wydział Matematyki i Informatyki: Zakład Matematyki Dyskretnej
URI: http://hdl.handle.net/10593/445
Appears in Collections:Doktoraty (WMiI)
Doktoraty 2010-2022 /dostęp otwarty/

Files in This Item:
File Description SizeFormat 
Rozprawa Doktorska 2010 Maciej Kalkowski.pdf360.55 kBAdobe PDFView/Open
Show full item record



Items in AMUR are protected by copyright, with all rights reserved, unless otherwise indicated.