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. / Mathematical Sciences / PHD (MATHEMATICS)
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:unisa/oai:umkn-dsp01.int.unisa.ac.za:10500/1684 |
| Date | 30 November 2005 |
| Creators | Singleton, Joy Elizabeth |
| Contributors | Bullock, F.E.S. (Dr.), Frick, M. (Prof.), djagegjj@unisa.ac.za |
| Source Sets | South African National ETD Portal |
| Language | English |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0029 seconds