Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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í toán học quốc tế đề tài: Spanning Trees of Bounded Degree. | Spanning Trees of Bounded Degree Andrzej Czygrinow Department of Mathematics Arizona State University Tempe Arizona 85287 U.S.A. andrzej@math.la.asu.edu Glenn Hurlbert Department of Mathematics Arizona State University Tempe Arizona 85287 U.S.A. hurlbert@math.la.asu.edu William Genghua Fan Department of Mathematics Arizona State University Tempe Arizona 85287 U.S.A. fan@math.la.asu.edu H. A. Kierstead Department of Mathematics Arizona State University Tempe Arizona 85287 U.S.A. kierstead@asu.edu T. Trotter Department of Mathematics Arizona State University Tempe Arizona 85287 U.S.A. trotter@asu.edu Submitted January 5 2001 Accepted October 2 2001. MR Subject Classifications 05C05 05C38 05C69 05C35. Abstract Dirac s classic theorem asserts that if G is a graph on n vertices and J G n 2 then G has a hamilton cycle. As is well known the proof also shows that if deg x deg y n 1 for every pair x y of independent vertices in G then G has a hamilton path. More generally S. Win has shown that if k 2 G is connected and X I deg x n 1 whenever I is a k-element independent set then G has a spanning tree T with A T k. Here we are interested in the structure of spanning trees under the additional assumption that G does not have a spanning tree with maximum degree less than k. We show that apart from a single exceptional class of graphs if 52xei deg x n 1 for every k-element independent set then G has a spanning caterpillar T with maximum degree k. Furthermore given a maximum path P in G we may require that P is the spine of T and that the set of all vertices whose degree in T is 3 or larger is independent in T. Research supported in part by the National Security Agency. Research supported in part by the National Science Foundation. THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 R33 1 1 Introduction We consider only finite simple graphs and use the standard notation degG x to denote the degree of a vertex in G. We also use J G and A G to denote respectively the minimum degree and