The independent domination number of a graph G, denoted i(G), is the minimum cardinality of a maximal independent set of G. A maximal independent set of cardinality i(G) in G we call an i(G)-set. In this paper we provide a constructive characterization of trees G that have two disjoint i(G)-sets.

The independent domination number of a graph G, denoted i(G), is the minimum cardinality of a maximal independent set of G. A maximal independent set of cardinality i(G) in G we call an i(G)-set. The graph G is called i-excellent if every vertex of G belongs to some i(G)-set. We provide a constructive characterization of i-excellent trees.

The complementary prism of a graph G is the graph formed from a disjoint union of G and its complement ̄G by adding the edges of a perfect matching between the corresponding vertices of G and G. We study independent domination numbers of complementary prisms. Exact values are determined for complementary prisms of paths, complete bipartite graphs, and subdivided stars. A natural lower bound on the independent domination number of a complementary prism is given, and graphs attaining this bound axe characterized. Then we show that the independent domination number behaves somewhat differently in complementary prisms than the domination and total domination numbers. We conclude with a sharp upper bound.

The complementary prism of a graph G is the graph formed from a disjoint union of G and its complement ̄G by adding the edges of a perfect matching between the corresponding vertices of G and G. We study independent domination numbers of complementary prisms. Exact values are determined for complementary prisms of paths, complete bipartite graphs, and subdivided stars. A natural lower bound on the independent domination number of a complementary prism is given, and graphs attaining this bound axe characterized. Then we show that the independent domination number behaves somewhat differently in complementary prisms than the domination and total domination numbers. We conclude with a sharp upper bound.

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.

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. / Mathematical Science / M. Sc. (Mathematics)

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. / Mathematical Science / M. Sc. (Mathematics)

We study the concept of strong equality of domination parameters. Let P1 and P2 be properties of vertex subsets of a graph, and assume that every subset of V(G) with property P2 also has property P1. Let ψ1(G) and ψ2(G), respectively, denote the minimum cardinalities of sets with properties P1 and P2, respectively. Then ψ1(G) ≤ ψ2(G). If ψ1(G)=ψ2(G) and every ψ1(G)-set is also a ψ2(G)-set, then we say ψ1(G) strongly equals ψ2(G), written ψ1(G) = ψ2(G). We provide a constructive characterization of the trees T such that γ(T) = i(T), where γ(T) and i(T) are the domination and independent domination numbers, respectively. A constructive characterization of the trees T for which γ(T) = γt(T), where γt(T) denotes the total domination number of T, is also presented.

The tree-free domination number y(G; -Fk), k ≥ 2, of a graph G is the minimum cardinality of a dominating set S in G such that the subgraph (S) induced by S contains no tree on k vertices as a (not necessarily induced) subgraph (equivalently, each component of (S) has cardinality less than k). When k = 2, the tree-free domination number is the independent domination number. We obtain a characterization of trees with equal domination and tree-free domination numbers. This generalizes a result of Cockayne et al. (A characterisation of (y,i)-trees. J. Graph Theory 34(4) (2000) 277-292).

Let G be a graph and G̅ be the complement of G. The complementary prism GG̅ of G is the graph formed from the disjoint union of G and G̅ by adding the edges of a perfect matching between the corresponding vertices of G and G̅. For example, if G is a 5-cycle, then GG̅ is the Petersen graph. In this paper we investigate independent domination in complementary prisms.