No description available.

Let G = (V,E) be a graph. A set R is a restrained dominating set (total restrained dominating set, resp.) if every vertex in V − R (V) is adjacent to a vertex in R and (every vertex in V −R) to a vertex in V −R. The restrained domination number of G (total restrained domination number of G), denoted by gamma_r(G) (gamma_tr(G)), is the smallest cardinality of a restrained dominating set (total restrained dominating set) of G. If T is a tree of order n, then gamma_r(T) is greater than or equal to (n+2)/3. We show that gamma_tr(T) is greater than or equal to (n+2)/2. Moreover, we show that if n is congruent to 0 mod 4, then gamma_tr(T) is greater than or equal to (n+2)/2 + 1. We then constructively characterize the extremal trees achieving these lower bounds. Finally, if G is a graph of order n greater than or equal to 2, such that both G and G' are not isomorphic to P_3, then gamma_r(G) + gamma_r(G') is greater than or equal to 4 and less than or equal to n +2. We provide a similar result for total restrained domination and characterize the extremal graphs G of order n achieving these bounds.

We will study various quantities related to connectivity of a graph. To this end, we look at Nordhaus-Gaddum type problems, which are problems where the same quantity is studied for a graph $G$ and its complement $G^c$ at the same time. For a graph $G$ on $n$ vertices with normalized Laplacian eigenvalues $0 = \lambda_1(G) \leq \lambda_2(G) \leq \cdots \leq \lambda_n(G)$ and graph complement $G^c$, we prove that \begin{equation*} \max\{\lambda_2(G),\lambda_2(G^c)\}\geq \frac{2}{n^2}. \end{equation*} We do this by way of lower bounding $\max\{i(G), i(G^c)\}$ and $\max\{h(G), h(G^c)\}$ where $i(G)$ and $h(G)$ denote the isoperimetric number and Cheeger constant of $G$, respectively. We also discuss some related Nordhaus-Gaddum questions.

The closed neighbourhood of a vertex in a graph is the vertex together with the set of adjacent vertices. A di®erentiating-dominating set, or identifying code, is a collection of vertices whose intersection with the closed neighbour- hoods of each vertex is distinct and nonempty. A di®erentiating-dominating set in a graph serves to uniquely identify all the vertices in the graph. Chapter 1 begins with the necessary de¯nitions and background results and provides motivation for the following chapters. Chapter 1 includes a summary of the lower identi¯cation parameters, °L and °d. Chapter 2 de- ¯nes co-distinguishable graphs and determines bounds on the number of edges in graphs which are distinguishable and co-distinguishable while Chap- ter 3 describes the maximum number of vertices needed in order to identify vertices in a graph, and includes some Nordhaus-Gaddum type results for the sum and product of the di®erentiating-domination number of a graph and its complement. Chapter 4 explores criticality, in which any minor modi¯cation in the edge or vertex set of a graph causes the di®erentiating-domination number to change. Chapter 5 extends the identi¯cation parameters to allow for orientations of the graphs in question and considers the question of when adding orientation helps reduce the value of the identi¯cation parameter. We conclude with a survey of complexity results in Chapter 6 and a collection of interesting new research directions in Chapter 7. / Mathematical Sciences / PhD (Mathematics)

The closed neighbourhood of a vertex in a graph is the vertex together with the set of adjacent vertices. A di®erentiating-dominating set, or identifying code, is a collection of vertices whose intersection with the closed neighbour- hoods of each vertex is distinct and nonempty. A di®erentiating-dominating set in a graph serves to uniquely identify all the vertices in the graph. Chapter 1 begins with the necessary de¯nitions and background results and provides motivation for the following chapters. Chapter 1 includes a summary of the lower identi¯cation parameters, °L and °d. Chapter 2 de- ¯nes co-distinguishable graphs and determines bounds on the number of edges in graphs which are distinguishable and co-distinguishable while Chap- ter 3 describes the maximum number of vertices needed in order to identify vertices in a graph, and includes some Nordhaus-Gaddum type results for the sum and product of the di®erentiating-domination number of a graph and its complement. Chapter 4 explores criticality, in which any minor modi¯cation in the edge or vertex set of a graph causes the di®erentiating-domination number to change. Chapter 5 extends the identi¯cation parameters to allow for orientations of the graphs in question and considers the question of when adding orientation helps reduce the value of the identi¯cation parameter. We conclude with a survey of complexity results in Chapter 6 and a collection of interesting new research directions in Chapter 7. / Mathematical Sciences / PhD (Mathematics)