Metody Algorytmiczne w Badaniach Siły Nieregularności Grafów
Loading...
Date
2010-06-11T12:13:03Z
Authors
Advisor
Editor
Journal Title
Journal ISSN
Volume Title
Publisher
Title alternative
Algorithmic Methods for the Irregularity Strength of Graphs
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.
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
Sponsor
Keywords
grafy, graphs, algorytmy, algorithms, siła nieregularności, irregularity strength, kolorowanie, coloring