tailieunhanh - Báo cáo toán học: "Irregularity strength of regular graphs"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Irregularity strength of regular graphs. | Irregularity strength of regular graphs Jakub Przybylo AGH University of Science and Technology Al. Mickiewicza 30 30-059 Krakow Poland przybylo@ Submitted Nov 12 2007 Accepted Jun 9 2008 Published Jun 13 2008 Mathematics Subject Classifications 05C78 Abstract Let G be a simple graph with no isolated edges and at most one isolated vertex. For a positive integer w a w-weighting of G is a map f E G 1 2 . wg. An irregularity strength of G s G is the smallest w such that there is a w-weighting of G for which 52e u2e f e 2e v2e f e for all pairs of different vertices u v 2 V G . A conjecture by Faudree and Lehel says that there is a constant c such that s G n c for each d-regular graph G d 2. We show that s G 16n 6. Consequently we improve the results by Frieze Gould Karonski and Pfender in some cases by a log n factor in this area as well as the recent result by Cuckler and Lazebnik. Keywords irregularity strength graph weighting regular graph 1 Introduction All graphs we consider are simple and finite. An edge u vg will be denoted by uv or vu for short at times. For a given graph G and its vertex v NG v dG v V G E G and J G or simply N v d v V E and Ố denote the set of neighbours and the degree of v in G the set of vertices the set of edges and the minimum degree of G respectively. By G D we mean an induced subgraph of G with the vertex set D c V G . A set V Vi V2 . Vk g of disjoint subsets of a set V is called a partition of V if the union of all elements of V is V and Vi 0 for every i. We shall denote as Pk a path of length k 1 and write Pk v1v2 . vk for short if vivi 1 are its consecutive edges i 1 2 . k 1. For a graph G and a finite set S of integers an S-weighting of G is an assignment f E G S. If S 1 2 . wg then we call f a w-weighting of G. Moreover f e is called the weight of an edge e 2 E G while the weight of v 2 V G is defined as f v 12u2N v f vu . A weighting f is irregular if the obtained weights of all vertices are different. The .