Closure operations and Hamiltonian properties of independent and total domination critical graphs.

摘要

When an edge is added to a graph, each of the parameters γ, i, and γt may change. When the addition of any edge causes the parameter under consideration to decrease, such a graph is referred to as γ-critical (domination critical), i-critical (independent domination critical), or γ t-critical (total domination critical), respectively. The graphs studied in this dissertation are the independent domination critical and total domination critical graphs.;Many properties of γt-critical graphs are established, and the γt-critical graphs with γt = 3 are studied in detail. It is known that all γt-critical graphs G with γt = 3 satisfy 2 ≤ diam(G) ≤ 3, and hence the hamiltonian properties of the diameter two and diameter three cases are studied separately.;A new closure for total domination critical graphs is defined and used to study the hamiltonian properties of 2-connected diameter three γ t-critical graphs with γt = 3. All such graphs are shown to contain a Hamilton path (and in most cases a Hamilton cycle), and several families of these graphs are characterised. The γt-critical graphs with γ t = 3 that contain a cut vertex were characterised by Haynes, Mynhardt, and van der Merwe. All such graphs have diameter three and contain a Hamilton path.;In general, the diameter two γt-critical graphs with γt = 3 cannot be characterised in terms of a finite number of forbidden subgraphs. However, all such graphs are shown to be hamiltonian if 2 ≤ δ ≤ 3. A characterisation of several infinite families of diameter two γt-critical graphs with γt = 3 and δ = 3 is given.;For i-critical graphs G with i = 3, it is established that when δ ≥ 3, the graph G is hamiltonian, and when δ = 2, there is exactly one family of non-hamiltonian graphs. In all cases, G has a Hamilton path provided it has more than six vertices. The hamiltonian properties of i-critical graphs are determined using a closure similar to one developed by Hanson. Furthermore, characterisations are given of the i-critical graphs with i = 3 that either contain a cut vertex or are 2-connected with δ = 2.