Please use this identifier to cite or link to this item: https://hdl.handle.net/10593/782
Title: Siła nieregularności grafów
Other Titles: Irregularity Strength of Graphs
Authors: Anholcer, Marcin
Advisor: Karoński, Michał. Promotor
Keywords: Siła nieregularności
Irregularity strength
Totalna wierzchołkowa
Total vertex
Siła nieregularności
Irregularity strength
Iloczynowa siła nieregularności
Product irregularity strength
Ważenie nieregularne
Irregular weighting
Issue Date: 28-Dec-2010
Abstract: 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.
One of the well-known facts about simple graphs is that in every such graph G there are at least two vertices of the same degree (it follows from the Pigeonhole Principle).The situation changes when we assign weights (being positive integers) either to the edges of G or to its edges and vertices and consider weighted degrees of vertices instead of the ordinary ones. Three graph parameters are considered in the thesis: irregularity strength s(G), total vertex irregularity strength tvs(G) and product irregularity strength ps(G). In the first chapter of the thesis upper bounds on tvs(G) of arbitrary graph G ar given. The author presents also the exact values of tvs(F), where F is a forest with no vertices of degree 2, and tvs(Cnk), where Cnk is the k-th power of cycle Cn.The second chapter contains the results on the irregularity strength, s(G). In particular, the exact value of s(Cnk) has been determined.In the last chapter the facts on the product irregularity strength are presented. The main results are the upper bounds on ps(G) for G being either cycle or grid of sufficiently many vertices.
Description: Wydział Matematyki i Informatyki: Zakład Matematyki Dyskretnej
URI: http://hdl.handle.net/10593/782
Appears in Collections:Doktoraty (WMiI)
Doktoraty 2010-2022 /dostęp otwarty/

Files in This Item:
File Description SizeFormat 
Anholcer_Marcin_doktorat.pdf753.34 kBAdobe PDFView/Open
Show full item record



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