For a graph G = (V, E), a set S ⊆ V is a total dominating set if every vertex in V is adjacent to some vertex in S. The smallest cardinality of any total dominating set is the total domination number γt(G). For an arbitrary edge e εE(Ḡ), γt(G) - 2 ≤ γt(G + e) ≤ γt(G); if the latter inequality is strict for each e ε E(Ḡ) ≠ φ, then G is said to be γt-critical. The criticality index of an edge e ε E(Ḡ) is γt(e) = γt(G) - γt(G + e). Let E(Ḡ) = [e1...,em} and S = ∑j=1m̄ci(ej). The criticality index of G is ci(G) = S/m̄. For any rational number k, 0 ≤ k ≤ 2, we construct a graph G with ci(G) = k. For 1 ≤ k ≤ 2, we construct graphs with this property that are γt-critical as well as graphs that are not γt-critical.

The domination subdivision number of a graph is the minimum number of edges that must be subdivided in order to increase the domination number of the graph. Likewise, the total domination subdivision number is the minimum number of edges that must be subdivided in order to increase the total domination number. First, this thesis provides a complete survey of established bounds on the domination subdivision number and the total domination subdivision number. Then in Chapter 4, new results regarding bounds on the total domination subdivision number are given. Finally, a characterization of the total domination subdivision number of caterpillars is presented in Chapter 5.

For a graph G = (V,E), we consider a bipartition {V1,V2} of the vertex set V by placing constraints on the vertices as follows. For every vertex v in Vi, we place a constraint on the number of neighbors v has in Vi and a constraint on the number of neighbors it has in V3-i. Using three values, namely 0 (no neighbors are allowed), 1 (at least one neighbor is required), and X (any number of neighbors are allowed) for each of the four constraints, results in 27 distinct types of bipartitions. The goal is to characterize graphs having each of these 27 types. We give characterizations for 21 out of the 27. Three other characterizations appear in the literature. The remaining three prove to be quite difficult. For these, we develop properties and give characterization of special families.

For graphs G and H, a set S⊆V(G) is an H-forming set of G if for every v∈V(G)-S, there exists a subset R⊆S, where |R|=|V(H)|-1, such that the subgraph induced by R∪{v} contains H as a subgraph (not necessarily induced). The minimum cardinality of an H-forming set of G is the H-forming number γ {H}(G). The H-forming number of G is a generalization of the domination number γ(G) because γ(G)=γ {P2}(G) . We show that γ(G)γ {P3}(G)γ t(G), where γ t(G) is the total domination number of G. For a nontrivial tree T, we show that γ {P3}(T)=γ t(T). We also define independent P 3-forming sets, give complexity results for the independent P 3-forming problem, and characterize the trees having an independent P 3-forming set.

For a graph G = (V, E), a subset S ⊆ V (G) is an equivalence dominating set if for every vertex v ∈ V (G) \ S, there exist two vertices u, w ∈ S such that the subgraph induced by {u, v, w} is a path. The equivalence domination number is the minimum cardinality of an equivalence dominating set of G, and the upper equivalence domination number is the maximum cardinality of a minimal equivalence dominating set of G. We explore relationships between total domination and equivalence domination. Then we determine the extremal graphs having large equivalence domination numbers.

Let u and v be vertices of a graph G, such that the distance between u and v is two and x is a common neighbor of u and v. We define the edge lift of uv off x as the process of removing edges ux and vx while adding the edge uv to G. In this paper, we investigate the effect that edge lifting has on the total domination number of a graph. Among other results, we show that there are no trees for which every possible edge lift decreases the total domination number and that there are no trees for which every possible edge lift leaves the total domination number unchanged. Trees for which every possible edge lift increases the total domination number are characterized.

For a graph G = (V, E), a subset S ⊆ V (G) is an equivalence dominating set if for every vertex v ∈ V (G) \ S, there exist two vertices u, w ∈ S such that the subgraph induced by {u, v, w} is a path. The equivalence domination number is the minimum cardinality of an equivalence dominating set of G, and the upper equivalence domination number is the maximum cardinality of a minimal equivalence dominating set of G. We explore relationships between total domination and equivalence domination. Then we determine the extremal graphs having large equivalence domination numbers.

Let u and v be vertices of a graph G, such that the distance between u and v is two and x is a common neighbor of u and v. We define the edge lift of uv off x as the process of removing edges ux and vx while adding the edge uv to G. In this paper, we investigate the effect that edge lifting has on the total domination number of a graph. Among other results, we show that there are no trees for which every possible edge lift decreases the total domination number and that there are no trees for which every possible edge lift leaves the total domination number unchanged. Trees for which every possible edge lift increases the total domination number are characterized.

A Roman dominating function (RDF) on a graph G is a function f : V (G) → (0, 1,2) satisfying the condition that every vertex u with f(u) = 0 is adjacent to at least one vertex v of G for which f(v) = 2. The weight of a Roman dominating function is the sum f(V ) = Σv∈Vf(v), and the minimum weight of a Roman dominating function f is the Roman domination number γR(G). An RDF f is called an independent Roman dominating function (IRDF) if the set of vertices assigned positive values under f is independent. The independent Roman domination number iR(G) is the minimum weight of an IRDF on G. We show that for every nontrivial connected graph G with maximum and i(G) are, respectively, the domination and independent domination numbers of G. Moreover, we characterize the connected graphs attaining each lower bound. We give an additional lower bound for γR(G) and compare our two new bounds on γR(G) with some known lower bounds.

A set S of vertices of a graph G is a dominating set if every vertex not in S is adjacent to a vertex of S and is a total dominating set if every vertex of G is adjacent to a vertex of S. The cardinality of a minimum dominating (total dominating) set of G is called the domination (total domination) number. A set that does not dominate (totally dominate) G is called a non-dominating (non-total dominating) set of G. A partition of the vertices of G into non-dominating (non-total dominating) sets is a non-dominating (non-total dominating) set partition. We show that the minimum number of sets in a non-dominating set partition of a graph G equals the total domination number of its complement Ḡ and the minimum number of sets in a non-total dominating set partition of G equals the domination number of Ḡ. This perspective yields new upper bounds on the domination and total domination numbers. We motivate the study of these concepts with a social network application.