TAILIEUCHUNG - Báo cáo toán học: " On cubic planar hypohamiltonian and hypotraceable graph"

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: On cubic planar hypohamiltonian and hypotraceable graphs. | On cubic planar hypohamiltonian and hypotraceable graphs Makoto Araya Department of Computer Science Shizuoka University Hamamatsu 432-8011 Japan araya@ Gabor Wiener Department of Computer Science and Information Theory Budapest University of Technology and Economics 1117 Budapest Magyar tudosok korutja 2. wiener@ Submitted Aug 4 2009 Accepted Apr 5 2011 Published Apr 14 2011 Mathematics Subject Classification 05C10 05C38 05C45 Abstract We present a cubic planar hypohamiltonian graph on 70 vertices improving the best known bound of 94 by Thomassen and derive some consequences concerning longest paths and cycles of planar 3-connected graphs. We also show that cubic planar hypohamiltonian graphs on n vertices exist for every even number n 86 and that cubic planar hypotraceable graphs exist on n vertices for every even number n 356 settling an open question of Holton and Sheehan. 1 Introduction Hamiltonian properties of planar cubic graphs have been investigated extensively since Tait s attempt to prove the four color conjecture based on the proposition that every 3-connected planar cubic graph has a Hamiltonian cycle. This proposition was disproved by Tutte 17 in 1946. However until 1968 when Grinberg 4 proved a simple yet very useful theorem such graphs were quite difficult to find. THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P85 1 Theorem . Grinberg 1968 Suppose a plane graph has a Hamiltonian cycle such that there are fi i-gons in the exterior of the Hamiltonian cycle and fi i-gons in the interior of the Hamiltonian cycle. Then i - 2 fi - fi 0 1 i The theorem can be used to create non-hamiltonian planar cubic graphs suppose for example that all but one faces of a plane graph have degree congruent to 2 modulo 3 then 1 clearly cannot hold so the graph cannot be Hamiltonian. Since 1968 several non-hamiltonian 3-connected planar cubic graphs have been found the smallest of them is the Barnette-Bosak-Lederberg graph on 38 vertices 2 10

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học