TAILIEUCHUNG - Báo cáo toán học: "Lower Bound for the Size of Maximal Nontraceable Graphs."

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: Lower Bound for the Size of Maximal Nontraceable Graphs. | Lower Bound for the Size of Maximal Nontraceable Graphs Marietjie Frick Joy Singleton University of South Africa . Box 392 Unisa 0003 South Africa. e-mail frickm@ singlje@ Submitted Jun 25 2004 Accepted Jul 4 2005 Published Jul 19 2005 2000 Mathematics Subject Classification 05C38 Abstract Let g n denote the minimum number of edges of a maximal nontraceable graph of order n. Dudek Katona and Wojda 2003 showed that g n p3n 1 2 for n 20 and g n p3n 1 for n 54 as well as for n 2 I 22 23 30 31 38 39 40 41 42 43 46 47 48 49 50 51 . We show that g n p3 1 for n 54 as well as for n 2 I u 12 13 and we determine g n for n 9. Keywords maximal nontraceable hamiltonian path traceable nontraceable nonhamiltonian 1 Introduction We consider only simple finite graphs G and denote the vertex set the edge set the order and the size of G by V G E G v G and e G respectively. The open neighbourhood of a vertex v in G is the set Ng v x 2 V G vx 2 E G . If U is a nonempty subset of V G then Ui denotes the subgraph of G induced by U. A graph G is hamiltonian if it has a hamiltonian cycle a cycle containing all the vertices of G and traceable if it has a hamiltonian path a path containing all the vertices of G . A graph G is maximal nonhamiltonian MNH if G is not hamiltonian but G e is hamiltonian for each e 2 E G where G denotes the complement of G. A graph G is maximal nontraceable MNT if G is not traceable but G e is traceable for each e 2 E G . This material is based upon research for a thesis at the University of South Africa and is supported by the National Research Foundation under Grant number 2053752. THE ELECTRONIC JOURNAL OF COMBINATORICS 12 2005 R32 1 In 1978 Bollobás 1 posed the problem of finding the least number of edges f n in a MNH graph of order n. Bondy 2 had already shown that a MNH graph with order n 7 that contained m vertices of degree 2 had at least 3n m 2 edges and hence f n d3n 2 for n 7. Combined results of Clark Entringer and Shapiro 3 4

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.