Siła nieregularności grafów

Loading...
Thumbnail Image

Date

2010-12-28T14:07:09Z

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.

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

Citation

ISBN

DOI

Title Alternative

Rights Creative Commons

Creative Commons License

Uniwersytet im. Adama Mickiewicza w Poznaniu
Biblioteka Uniwersytetu im. Adama Mickiewicza w Poznaniu
Ministerstwo Nauki i Szkolnictwa Wyższego