Siła nieregularności grafów
Loading...
Date
2010-12-28T14:07:09Z
Authors
Advisor
Editor
Journal Title
Journal ISSN
Volume Title
Publisher
Title alternative
Irregularity Strength of Graphs
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.
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
Sponsor
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