tailieunhanh - Báo cáo toán học: " Neighbour-distinguishing edge colourings of random 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: Neighbour-distinguishing edge colourings of random regular graphs. | Neighbour-distinguishing edge colourings of random regular graphs Catherine Greenhill School of Mathematics and Statistics University of New South Wales Sydney NSW 2052 Australia csg@ Andrzej Rucinski Department of Discrete Mathematics Adam Mickiewicz University Poznan Poland rucinski@ Submitted Dec 26 2005 Accepted Aug 10 2006 Published Aug 25 2006 Abstract A proper edge colouring of a graph is neighbour-distinguishing if for all pairs of adjacent vertices v w the set of colours appearing on the edges incident with v is not equal to the set of colours appearing on the edges incident with w. Let ndi G be the least number of colours required for a proper neighbour-distinguishing edge colouring of G. We prove that for d 4 a random d-regular graph G on n vertices asymptotically almost surely satishes ndi G 3d 2 . This verihes a conjecture of Zhang Liu and Wang for almost all 4-regular graphs. 1 Introduction Suppose that G V E is a graph and h E k is a proper edge colouring of G. All edge colourings considered in this paper are proper and from now on we will not explicitly mention this. For each vertex v 2 V let S v h e v 2 eg be the set of colours on the neighbourhood of v. An edge colouring h is said to be neighbour-distinguishing if S v S w for all v Wg 2 E .A neighbour-distinguishing edge colouring of G exists if G has no isolated edges. Let the neighbour-distinguishing index of G denoted by ndi G be the least number of colours needed in a neighbour-distinguishing edge colouring of G where ndi G 1 if G contains an isolated edge . We sometimes abbreviate neighbourdistinguishing edge colouring to nd-colouring . This notion was introduced by Zhang Liu and Wang in 12 . Note that nd-colourings are also called strong edge colourings 12 or adjacent vertex distinguishing colourings 2 . Our terminology and notation follows 4 . Research supported by the UNSW Faculty Research Grants Scheme. THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R77 1 As an .