Two conjectures on 3-domination critical graphs
Loading...
Authors
Moodley, Lohini
Issue Date
1999-01
Type
Dissertation
Language
Keywords
Domination , Independent domination , Hamiltonicity , Domination-critical graphs
Alternative Title
Abstract
For a graph G = (V (G), E (G)), a set S ~ V (G) dominates G if each vertex
in V (G) \S is adjacent to a vertex in S. The domination number I (G) (independent
domination number i (G)) of G is the minimum cardinality amongst its dominating
sets (independent dominating sets). G is k-edge-domination-critical, abbreviated k-1-
critical, if the domination number k decreases whenever an edge is added. Further, G
is hamiltonian if it has a cycle that passes through each of its vertices.
This dissertation assimilates research generated by two conjectures:
Conjecture I. Every 3-1-critical graph with minimum degree at least two is hamiltonian.
Conjecture 2. If G is k-1-critical, then I ( G) = i ( G).
The recent proof of Conjecture I is consolidated and presented accessibly. Conjecture
2 remains open for k = 3 and has been disproved for k :::>: 4. The progress is
detailed and proofs of new results are presented.
Description
Citation
Moodley, Lohini (1999) Two conjectures on 3-domination critical graphs, University of South Africa, Pretoria, <http://hdl.handle.net/10500/17505>