TAILIEUCHUNG - 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 .

TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN
TAILIEUCHUNG - Chia sẻ tài liệu không giới hạn
Địa chỉ : 444 Hoang Hoa Tham, Hanoi, Viet Nam
Website : tailieuchung.com
Email : tailieuchung20@gmail.com
Tailieuchung.com là thư viện tài liệu trực tuyến, nơi chia sẽ trao đổi hàng triệu tài liệu như luận văn đồ án, sách, giáo trình, đề thi.
Chúng tôi không chịu trách nhiệm liên quan đến các vấn đề bản quyền nội dung tài liệu được thành viên tự nguyện đăng tải lên, nếu phát hiện thấy tài liệu xấu hoặc tài liệu có bản quyền xin hãy email cho chúng tôi.
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.