کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6423669 1632577 2016 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On constructions of hypotraceable graphs
ترجمه فارسی عنوان
بر روی ساختار گرافهای قابل قبول
کلمات کلیدی
نمودار قابل قبول گراف هیپو هامیلتون نمودار تقریبا هیو هامیلتون
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

A graph G is hypohamiltonian/hypotraceable if it is not hamiltonian/traceable, but all vertex deleted subgraphs of G are hamiltonian/traceable. Until now all hypotraceable graphs were constructed using hypohamiltonian graphs; extending a method of Thomassen [C. Thomassen, Hypohamiltonian and hypotraceable graphs, Discrete Mathematics 9 (1974), 91-96] we present a construction that uses so-called almost hypohamiltonian graphs (nonhamiltonian graphs, whose vertex deleted subgraphs are hamiltonian with exactly one exception). As an application, we construct a planar hypotraceable graph of order 138, improving the best known bound of 154 [M. Jooyandeh, B. D. McKay, P. R. J. Östergård, V. H. Pettersson, C. T. Zamfirescu, Planar Hypohamiltonian Graphs on 40 Vertices, J. Graph Theory DOI: 10.1002/jgt.22015 (2016)]. We also prove a structural type theorem showing that hypotraceable graphs possessing some connectivity properties are all built using either Thomassen's or our method.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 54, October 2016, Pages 127-132
نویسندگان
,