tailieunhanh - Báo cáo toán học: "A note on neighbour-distinguishing regular graphs total-weightin"

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: A note on neighbour-distinguishing regular graphs total-weighting. | A note on neighbour-distinguishing regular graphs total-weighting Jakub Przybylo AGH University of Science and Technology Al. Mickiewicza 30 30-059 Krakow Poland przybylo@ Submitted May 22 2007 Accepted Sep 4 2008 Published Sep 15 2008 Mathematics Subject Classifications 05C78 Abstract We investigate the following modification of a problem posed by Karonski Luczak and Thomason J. Combin. Theory Ser. B 91 2004 151-157 . Let us assign positive integers to the edges and vertices of a simple graph G. As a result we obtain a vertex-colouring of G by sums of weights assigned to the vertex and its adjacent edges. Can we obtain a proper colouring using only weights 1 and 2 for an arbitrary G We know that the answer is yes if G is a 3-colourable complete or 4-regular graph. Moreover it is enough to use weights from 1 to 11 as well as from 1 to L F J 1 for an arbitrary graph G. Here we show that weights from 1 to 7 are enough for all regular graphs. Keywords neighbour-distinguishing total-weighting regular graph 1 Introduction A k-total-weighting of a simple graph G is an assignment of an integer weight w e w v 2 1 . k to each edge e and each vertex v of G. A k-total-weighting is neighbourdistinguishing or vertex colouring see 1 2 if for every edge uv w u e3u w e w v Ee3 w e . If such a weighting exists we say that G permits a neighbourdistinguishing k-total-weighting. A similar parameter but in the case of an edge not total weighting was introduced and studied in 3 by Karonski Luczak and Thomason. They asked if each simple connected graph that is not simply a single edge permits a neighbour-distinguishing 3-edge-weighting and showed that this statement holds for 3-colourable graphs. Then Addario-Berry Dalal and Reed showed that it is enough to use numbers from 1 to 16 to construct THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 N35 1 a neighbour-distinguishing edge-weighting for an arbitrary graph not containing a single edge as a component see 2 . In 4 we