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