Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo tin học: "Spanning Trees with Many Leaves and Average Distance"

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: Spanning Trees with Many Leaves and Average Distance. | Spanning Trees with Many Leaves and Average Distance Ermelinda DeLaVina and Bill Waller Department of Computer and Mathematical Sciences University of Houston-Downtown Houston TX 77002 delavinae@uhd.edu wallerw@uhd.edu Submitted Sep 18 2006 Accepted Jan 30 2008 Published Feb 11 2008 Mathematics Subject Classification 05C35 Abstract In this paper we prove several new lower bounds on the maximum number of leaves of a spanning tree of a graph related to its order independence number local independence number and the maximum order of a bipartite subgraph. These new lower bounds were conjectured by the program Graffiti.pc a variant of the program Graffiti. We use two of these results to give two partial resolutions of conjecture 747 of Graffiti circa 1992 which states that the average distance of a graph is not more than half the maximum order of an induced bipartite subgraph. If correct this conjecture would generalize conjecture number 2 of Graffiti which states that the average distance is not more than the independence number. Conjecture number 2 was first proved by F. Chung. In particular we show that the average distance is less than half the maximum order of a bipartite subgraph plus one-half we also show that if the local independence number is at least five then the average distance is less than half the maximum order of a bipartite subgraph. In conclusion we give some open problems related to average distance or the maximum number of leaves of a spanning tree. Introduction and Key Definitions Graffiti a computer program that makes conjectures was written by S. Fajtlowicz and dates from the mid-1980 s. Graffiti.pc a program that makes graph theoretical conjectures utilizing conjecture making strategies similar to those found in Graffiti was written by E. DeLaVina. The operation of Graffiti.pc and its similarities to Graffiti are described in 10 and 11 its conjectures can be found in 13 . A numbered annotated listing of several hundred of Graffiti s conjectures