Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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: Maximal Nontraceable Graphs with Toughness less than One. | Maximal Nontraceable Graphs with Toughness less than One Frank Bullock Marietjie Frick Joy Singleton Susan van Aardt University of South Africa P.O. Box 392 Unisa 0003 South Africa. bullofes@unisa.ac.za frickm@unisa.ac.za singlje@unisa.ac.za vaardsa@unisa.ac.za Kieka C.M. Mynhardtz University of Victoria P.O. Box 3045 Victoria BC Canada V8W 3P4. mynhardt@math.uvic.ca Submitted Jun 21 2006 Accepted Jan 14 2008 Published Jan 21 2008 Mathematics Subject Classification 05C38 Abstract A graph G is maximal nontraceable MNT if G does not have a hamiltonian path but for every e 2 E G the graph G e has a hamiltonian path. A graph G is 1-tough if for every vertex cut S of G the number of components of G S is at most S . We investigate the structure of MNT graphs that are not 1-tough. Our results enable us to construct several interesting new classes of MNT graphs. Keywords maximal nontraceable hamiltonian path traceable nontraceable toughness 1 Introduction We consider only simple finite graphs. We denote the vertex set the edge set the order and the size of a graph G by V G E G v G and e G respectively. The open This material is based upon work supported by the National Research Foundation under Grant number 2053752 and Thuthuka Grant number TTK2005081000028. y Corresponding author. z Visit to University of South Africa while this paper was written supported by the Canadian National Science and Engineering Research Council. THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R18 1 neighbourhood of a vertex v in G is the set NG v x 2 V G vx 2 E G g. If Ng v u vg V G we call v a universal vertex of 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 . If a graph G has a hamiltonian path with endvertices x and y we say that G is traceable from x to y. If G is traceable from