tailieunhanh - Báo cáo toán học: "Graceful Tree Conjecture for Infinite Trees"

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: Graceful Tree Conjecture for Infinite Trees. | Graceful Tree Conjecture for Infinite Trees Tsz Lung Chan Department of Mathematics The University of Hong Kong Pokfulam Hong Kong h0592107@ Wai Shun Cheung Department of Mathematics The University of Hong Kong Pokfulam Hong Kong wshun@ Tuen Wai Ng Department of Mathematics The University of Hong Kong Pokfulam Hong Kong ntw@ Submitted Sep 26 2007 Accepted May 19 2009 Published May 29 2009 Abstract One of the most famous open problems in graph theory is the Graceful Tree Conjecture which states that every finite tree has a graceful labeling. In this paper we define graceful labelings for countably infinite graphs and state and verify a Graceful Tree Conjecture for countably infinite trees. 1 Introduction The study of graph labeling was initiated by Rosa 9 in 1967. This involves labeling vertices or edges or both using integers subject to certain conditions. Ever since then various kinds of graph labelings have been considered and the most well-studied ones are graceful magic and harmonious labelings. Not only interesting in its own right graph labeling also finds a broad range of applications the study of neofields topological graph theory coding theory radio channel assignment communication network addressing and database management. One should refer to the comprehensive survey by Gallian 6 for further details. THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 R65 1 Rosa 9 considered the p-valuation which is commonly known as graceful labeling. A graceful labeling of a graph G with n edges is an injective function f V G 0 1 . n such that when each edge xy G E G is assigned the edge label If x f y all the edge labels are distinct. A graph is graceful if it admits a graceful labeling. Graceful labeling was originally introduced to attack Ringel s Conjecture which says that a complete graph of order 2n 1 can be decomposed into 2n 1 isomorphic copies of any tree with n edges. Rosa showed that Ringel s Conjecture is true if every