Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Building Graphs from Colored Trees. | Building Graphs from Colored Trees Rachel M. Esselstein CSUMB Department of Mathematics and Statistics 100 Campus Center Dr. Building 53 Seaside CA 93955 . resselstein@ Peter Winkler Department of Mathematics Kemeny Hall Dartmouth College Hanover NH 03755 . Submitted Sep 7 2009 Accepted Oct 7 2010 Published Nov 26 2010 Mathematics Subject Classification 05C85 Abstract We will explore the computational complexity of satisfying certain sets of neighborhood conditions in graphs with various properties. More precisely fix a radius p and let N G be the set of isomorphism classes of p-neighborhoods of vertices of G where G is a graph whose vertices are colored not necessarily properly by colors from a fixed finite palette. The root of the neighborhood will be the unique vertex at the center of the graph. Given a set S of colored graphs with a unique root when is there a graph G with N G S Or N G c S What if G is forced to be infinite or connected or both If the neighborhoods are unrestricted all these problems are recursively unsolv-able this follows from the work of Bulitko Graphs with prescribed environments of the vertices. Trudy Mat. Inst. Steklov. 133 78-94 274 1973 . In contrast when the neighborhoods are cycle free all the problems are in the class P. Surprisingly if G is required to be a regular and thus infinite tree we show the realization problem is NP-complete for degree 3 and higher whereas if G is allowed to be any finite graph the realization problem is in P. Research supported in part by NSF Grant DMS-0600876 THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R161 1 1 Introduction The notion of a neighborhood will be used throughout this paper in two different ways. Formally the neighborhood of radius p of a vertex v in graph G is the subgraph given by the set of all vertices reachable from v in G by a path of length p and the corresponding edges from G. We say that v is the center of this neighborhood. In this
