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í Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Hamiltonicity of k-Traceable Graphs. | Hamiltonicity of k-Traceable Graphs 1Frank Bullock 2Peter Dankelmann 1Marietjie Frick 3Michael A. Henningl 4Ortrud R. OellermannỊ and 1 Susan van Aardt University of South Africa Pretoria bullofes Vaardsa @ 2University of KwaZulu-Natal Westville Campus dankelma@ 3University of Johannesburg Johannesburg mahenning@ 4University of Winnipeg Winnipeg Submitted Jun 15 2009 Accepted Mar 2 2011 Published Mar 24 2011 Mathematics Subject Classification 05C38 05C45 Abstract Let G be a graph. A Hamilton path in G is a path containing every vertex of G. The graph G is traceable if it contains a Hamilton path while G is k-traceable if every induced subgraph of G of order k is traceable. In this paper we study hamiltonicity of k-traceable graphs. For k 2 an integer we define H k to be the largest integer such that there exists a k-traceable graph of order H k that is nonhamiltonian. For k 10 we determine the exact value of H k . For k 11 we show that k 2 H k 21 3k 5 . Keywords Hamiltonian graph traceable toughness AMS subject classification 05C38 05C45 Research supported in part by the South African National Research Foundation grant number 2053752 1 Research supported in part by the South African National Research Foundation Research supported in part by an NSERC grant Canada Research supported in part by the South African National Research Foundation grant number TTK2004080300021 THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P63 1 1 Introduction For notation and graph theory terminology we in general follow 14 . Specifically let G V E be a graph with vertex set V of order n V and edge set E of size m E and let v be a vertex in V. The open neighborhood of v is the set N v u G V uv G E . For a set S of vertices the open neighborhood of S is defined by N S UveSN v . If A and B are subsets of V G then we sometimes denote N A n B by NB A and if H and J are subgraphs of G then we write NJ H for NV J V
