Wydział Matematyki i Informatyki (WMiI)/Faculty of Mathematics and Computer Science

Permanent URI for this community

Now showing 1 - 1 of 1

Siła nieregularności grafów
(2010-12-28T14:07:09Z) Anholcer, Marcin; Karoński, Michał. Promotor
Jednym z lepiej znanych faktów na temat grafów prostych jest to, że każdy z nich posiada co najmniej dwa wierzchołki tego samego stopnia (fakt ten wynika z zasady szufladkowej).Sytuacja zmienia się, gdy przypisujemy wagi (będące liczbami naturalnymi) krawędziom, bądź krawędziom i wierzchołkom G i rozważamy ważone stopnie wierzchołków zamiast zwykłych. W pracy rozważane są trzy parametry: siła nieregularności s(G), totalna wierzchołkowa siła nieregularności tvs(G) i iloczynowa siła nieregularności ps(G).W pierwszym rozdziale pracy zostały podane górne ograniczenia na tvs(G) dla dowolnego grafu G. Autor przedstawia również dokładne wartości tvs(F), gdzie F jest lasem nie posiadającym wierzchołków stopnia 2, i tvs(Cnk), gdzie Cnk jest k-tą potęgą cyklu Cn.Drugi rozdział zawiera rezultaty na temat siły nieregularności, s(G). W szczególności, wyznaczono dokładną wartość s(Cnk).W ostatnim rozdziale przedstawione zostały fakty na temat iloczynowej siły nieregularności. Głównymi rezultatami są górne ograniczenia na ps(G), gdzie G jest cyklem albo kratą o wystarczająco wielu wierzchołkach.