TAILIEUCHUNG - Báo cáo toán học: "The Fibonacci dimension of a graph"

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: The Fibonacci dimension of a graph. | The Fibonacci dimension of a graph Sergio Cabello David Eppstein Sandi Klavzad Submitted Mar 13 2009 Accepted Feb 28 2011 Published Mar 11 2011 Mathematics Subject Classification 05C12 05C75 05C85 Abstract The Fibonacci dimension fdim G of a graph G is introduced as the smallest integer f such that G admits an isometric embedding into Tf the f-dimensional Fibonacci cube. We give bounds on the Fibonacci dimension of a graph in terms of the isometric and lattice dimension provide a combinatorial characterization of the Fibonacci dimension using properties of an associated graph and establish the Fibonacci dimension for certain families of graphs. From the algorithmic point of view we prove that it is NP-complete to decide whether fdim G equals the isometric dimension of G and show that no algorithm to approximate fdim G has approximation ratio below 741 740 unless P NP. We also give a 3 2 -approximation algorithm for fdim G in the general case and a 1 -approximation algorithm for simplex graphs. 1 Introduction Hypercubes play a prominent role in metric graph theory as well as in several other areas such as parallel computing and coding theory. One of their central features is the ability to compute distances very efficiently because the distance between two vertices is simply the number of coordinates in which they differ the same ability to compute distances may be transferred to any isometric subgraph of a hypercube. In this way partial cubes appear a class of graphs intensively studied so far see the books 12 19 32 the recent papers 3 25 43 44 the recent semi- survey 42 and references therein. In particular we point out a recent fast recognition algorithm 17 and improvements in classification of cubic partial cubes 16 37 . Faculty of Mathematics and Physics University of Ljubljana Jadranska 19 1000 Ljubljana Slovenia Institute of Mathematics Physics and Mechanics Jadranska 19 1000 Ljubljana Slovenia. E-mail . Computer Science Department

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học