Wiener, Gábor (2016) On constructions of hypotraceable graphs. ELECTRONIC NOTES IN DISCRETE MATHEMATICS. ISSN 1571-0653 (In Press)
|
Text
barcelona16.pdf Download (217kB) | Preview |
Abstract
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 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. 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.
| Item Type: | Article |
|---|---|
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika > QA166-QA166.245 Graphs theory / gráfelmélet Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány |
| Depositing User: | Dr. Gábor Wiener |
| Date Deposited: | 29 Sep 2016 12:44 |
| Last Modified: | 29 Sep 2016 12:44 |
| URI: | http://real.mtak.hu/id/eprint/40505 |
Actions (login required)
 |
Edit Item |
