Institutional Repository

Maximal nontraceable graphs

Show simple item record

dc.contributor.advisor Bullock, F.E.S. (Dr.) en
dc.contributor.advisor Frick, M. (Prof.) en Singleton, Joy Elizabeth en 2009-08-25T10:55:38Z 2009-08-25T10:55:38Z 2009-08-25T10:55:38Z 2005-11-30 en
dc.identifier.citation Singleton, Joy Elizabeth (2009) Maximal nontraceable graphs, University of South Africa, Pretoria, <> en
dc.description.abstract A graph G is maximal nontraceable (MNT) (maximal nonhamiltonian (MNH)) if G is not traceable (hamiltonian), i.e. does not contain a hamiltonian path (cycle), but G+xy is traceable (hamiltonian) for all nonadjacent vertices x and y in G. A graph G is hypohamiltonian if G is not hamiltonian, but every vertex deleted subgraph G -u of G is hamiltonian. A graph which is maximal nonhamiltonian and hypohamiltonian is called maximal hypohamiltonian (MHH). Until recently, not much has appeared in the literature about MNT graphs, although there is an extensive literature on MNH graphs. In 1998 Zelinka constructed two classes of MNT graphs and made the conjecture, which he later retracted, that every MNT graph belongs to one of these classes. We show that there are many different types of MNT graphs that cannot be constructed by Zelinka's methods. Although we have not been able to characterize MNT graphs in general, our attempt at characterizing MNT graphs with a specified number of blocks and cut-vertices enabled us to construct infinite families of non-Zelinka MNT graphs which have either two or three blocks. We consider MNT graphs with toughness less than one, obtaining results leading to interesting constructions of MNT graphs, some based on MHH graphs. One result led us to discover a non-Zelinka MNT graph of smallest order, namely of order 8. We also present examples of MNTgraphs with toughness at least one, including an infinite family of 2-connected, claw-free graphs. We find a lower bound for the size of 2-connected MNT graphs of order n. We construct an infinite family of 2-connected cubic MNT graphs of order n, using MHH graphs as building blocks. We thus find the minimum size of 2-connected MNT graphs for infinitely many values of n. We also present a construction, based on MHH graphs, of an infinite family of MNT graphs that are almost cubic. We establish the minimum size of MNT graphs of order n, for all except 26 values of n, and we present a table of MNT graphs of possible smallest size for the excluded 26 values of n. en
dc.language.iso en en
dc.subject graph theory en
dc.subject hamiltonian path en
dc.subject traceable en
dc.subject nontraceable en
dc.subject maximal nontraceable en
dc.subject hamiltonian cycle en
dc.subject hamiltonian en
dc.subject nonhamiltonian en
dc.subject maximal nonhamiltonian en
dc.subject hypohamiltonian en
dc.subject maximal hypohamiltonian en
dc.subject hamiltonian-connected en
dc.subject maximal nonhamiltonian-connected en
dc.title Maximal nontraceable graphs en
dc.type Thesis en en
dc.description.department Mathematical Sciences en PHD (MATHEMATICS) en

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search UnisaIR


My Account