TAILIEUCHUNG - Báo cáo toán học: "A Simple Method for Constructing Small Cubic Graphs of Girths 14, 15, and 16"

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: A Simple Method for Constructing Small Cubic Graphs of Girths 14, 15, and 16. | A Simple Method for Constructing Small Cubic Graphs of Girths 14 15 and 16 Geoffrey Exoo Department of Mathematics and Computer Science Indiana State University Terre Haute IN 47809 Submitted September 20 1996 Accepted September 26 1996 Abstract A method for constructing cubic graphs with girths in the range 13 to 16 is described. The method is used to construct the smallest known cubic graphs for girths 14 15 and 16. Introduction We consider the problem of finding smallest regular graphs with given girth and degree the cage problem. This problem has a prominent place in both Extremal and Algebraic Graph Theory. Biggs book on Algebraic Graph Theory 1 provides an introduction to this subject. Wong s survey article 3 gives a comprehensive picture of the state of the art in 1982. In this note we shall be specifically interested in cubic trivalent cages and note that the current status of the problem can be obtained from Gordon Royle 2 . The General Construction We describe a family of cubic graphs with girths in the stated range. We begin with a description of a type of generalized Petersen graph that does not quite achieve our girth objectives and then consider adjustments to the construction that will increase the girth. Let T be a cubic tree a tree in which each vertex has degree 1 or 3 on t vertices. Then t is even and r t 2 1 is the number of endvertices. Let T1 . Tn be n copies of T. Suppose the 1 THE ELECTRONIC JOURNAL OF COMBINATORICS 3 1996 R30 2 vertices of Tị are labeled vi 0 . Vi t-1 so that vertices vi 0 . vi r-l are the endvertices. Initially we require that the mapping from Ti to Tj given by vi k Vj k be an isomorphism for all i and j. In this case we can obtain a simple generalization of the Petersen graph by choosing r positive integers hl. hr hi n 2 and joining vertex vi k to vi hi k. This gives a trivalent graph. It will be convenient to call the edges in one of the Tj s tree edges and the edges joining two of the trees chords. Note that for the .

TÀI LIỆU LIÊN QUAN
TAILIEUCHUNG - Chia sẻ tài liệu không giới hạn
Địa chỉ : 444 Hoang Hoa Tham, Hanoi, Viet Nam
Website : tailieuchung.com
Email : tailieuchung20@gmail.com
Tailieuchung.com là thư viện tài liệu trực tuyến, nơi chia sẽ trao đổi hàng triệu tài liệu như luận văn đồ án, sách, giáo trình, đề thi.
Chúng tôi không chịu trách nhiệm liên quan đến các vấn đề bản quyền nội dung tài liệu được thành viên tự nguyện đăng tải lên, nếu phát hiện thấy tài liệu xấu hoặc tài liệu có bản quyền xin hãy email cho chúng tôi.
Đã 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.