TAILIEUCHUNG - Báo cáo toán học: "Spanning Trees of Bounded Degree"

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 . andrzej@ Glenn Hurlbert Department of Mathematics Arizona State University Tempe Arizona 85287 . hurlbert@ William Genghua Fan Department of Mathematics Arizona State University Tempe Arizona 85287 . fan@ H. A. Kierstead Department of Mathematics Arizona State University Tempe Arizona 85287 . kierstead@ T. Trotter Department of Mathematics Arizona State University Tempe Arizona 85287 . trotter@ 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

TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.