For any graph parameter, the removal of a vertex from a graph can increase the parameter, decrease the parameter, or leave the parameter unchanged. This dissertation focuses on the case where the removal of a vertex decreases the parameter for the cases of independent domination and total domination. A graph is said to be independent domination vertex-critical, or i-critical, if the removal of any vertex decreases the independent domination number. Likewise, a graph is said to be total domination vertex-critical if the removal of any vertex decreases the total domination number. Following these notions, a graph is independent domination bicritical, or i-bicritical, if the removal of any two vertices decreases the independent domination number, and a graph is total domination bicritical if the removal of any two vertices decreases the total domination number. Additionally, a graph is called strong independent domination bicritical, or strong i-bicritical, if the removal of any two independent vertices decreases the independent domination number by two.
Construction results for i-critical graphs, i-bicritical graphs, strong i-bicritical graphs, total domination critical graphs, and total domination bicritical graphs are studied. Many known constructions are extended to provide necessary and sufficient conditions to build critical and bicritical graphs. New constructions are also presented, with a concentration on i-critical graphs. One particular construction shows that for any graph G, there exists an i-critical, i-bicritical, and strong i-bicritical graph H such that G is an induced subgraph of H. Structural properties of i-critical graphs, i-bicritical graphs, total domination critical graphs, and total domination bicritical graphs are investigated, particularly for the connectedness and edge-connectedness of critical and bicritical graphs. The coalescence construction, which has appeared in earlier literature, constructs a graph with a cut-vertex and this construction is studied in great detail for i-critical graphs, i-bicritical graphs, total domination critical graphs, and total domination bicritical graphs. It is also shown that strong i-bicritical graphs are 2-connected and thus the coalescence construction is not useful in this case.
Domination vertex-critical graphs (graphs where the removal of any vertex decreases the domination number) have been studied in the literature. A well-known result gives an upper bound on the diameter of such graphs. Here similar techniques are used to provide upper bounds on the diameter for i-critical graphs, strong i-bicritical graphs, and total domination critical graphs. The upper bound for the diameter of i-critical graphs trivially gives an upper bound for the diameter of i-bicritical graphs.
For a graph G, the gamma-graph of G is the graph where the vertex set is the collection of minimum dominating sets of G. Adjacency between two minimum dominating sets in the gamma-graph occurs if from one minimum dominating set a vertex can be removed and replaced with a vertex to arrive at the other minimum dominating set. One can think of adjacency between minimum dominating sets in the gamma-graph as a swap of two vertices between minimum dominating sets. In the single vertex replacement adjacency model these two vertices can be any vertices in the minimum dominating sets, and in the slide adjacency model these two vertices must be adjacent in G. (Hence the gamma-graph obtained from the slide adjacency model is a subgraph of the gamma-graph obtained in the single vertex replacement adjacency model.) Results for both adjacency models are presented concerning the maximum degree, the diameter, and the order of the gamma-graph when G is a tree. / Graduate / 0405 / michaedwards@gmail.com
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/6097 |
| Date | 30 April 2015 |
| Creators | Edwards, Michelle |
| Contributors | MacGillivray, Gary |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Rights | Available to the World Wide Web, http://creativecommons.org/licenses/by-nc-sa/2.5/ca/ |
Page generated in 0.0033 seconds