The main focus of this thesis is to evaluate .k_r(n,\delta)., the minimal number of $r$-cliques in graphs with $n$ vertices and minimum degree~$\delta$. A fundamental result in Graph Theory states that a triangle-free graph of order $n$ has at most $n 2/4$ edges. Hence, a triangle-free graph has minimum degree at most $n/2$, so if $k_3(n,\delta) =0$ then $\delta \le n/2$. For $n/2 \leq \delta \leq 4n/5$, I have evaluated $k_r(n,\delta)$ and determined the structures of the extremal graphs. For $\delta \ge 4n/5$, I give a conjecture on $k_r(n,\delta)$, as well as the structures of these extremal graphs. Moreover, I have proved various partial results that support this conjecture. Let $k_r �(n, \delta)$ be the analogous version of $k_r(n,\delta)$ for regular graphs. Notice that there exist $n$ and $\delta$ such that $k_r(n, \delta) =0$ but $k_r �(n, \delta) >0$. For example, a theorem of Andr{\'a}sfai, Erd{\H}s and S{\'o}s states that any triangle-free graph of order $n$ with minimum degree greater than $2n/5$ must be bipartite. Hence $k_3(n, \lfloor n/2 \rfloor) =0$ but $k_3 �(n, \lfloor n/2 \rfloor) >0$ for $n$ odd. I have evaluated the exact value $k_3 �(n, \delta)$ for $\delta$ between $2n/5+12 \sqrt{n}/5$ and $n/2$ and determined the structure of these extremal graphs. At the end of the thesis, I investigate a question in Ramsey Theory. The Ramsey number $R_k(G)$ of a graph $G$ is the minimum number $N$, such that any edge colouring of $K_N$ with $k$ colours contains a monochromatic copy of $G$. The constrained Ramsey number $f(G,T)$ of two graphs $G$ and $T$ is the minimum number $N$ such that any edge colouring of $K_N$ with any number of colours contains a monochromatic copy of $G$ or a rainbow copy of $T$. It turns out that these two quantities are closely related when $T$ is a matching. Namely, for almost all graphs $G$, $f(G,tK_2) =R_{t-1}(G)$ for $t \geq 2$.

No description available.

The minimum degree spanning tree problem is a widely studied NP-hard variation of the minimum spanning tree problem, and a generalization of the Hamiltonian path problem. Most of the work done on the minimum degree spanning tree problem has been on approximation algorithms, and very little work has been done studying graph classes where this problem may be polynomial time solvable. The Hamiltonian path problem has been widely studied on graph classes, and we use classes with polynomial time results for the Hamiltonian path problem as a starting point for graph class results for the minimum degree spanning tree problem. We show the minimum degree spanning tree problem is polynomial time solvable for chain graphs. We then show this problem is polynomial time solvable on bipartite permutation graphs, and that there exist minimum degree spanning trees of these graphs that are caterpillars, and that have other particular structural properties.

A total dominating set of a graph G with no isolated vertex is a set 5 of vertices of G such that every vertex is adjacent to a vertex in S. The total domination number of G is the minimum cardinality of a total dominating set in G. In this paper, we present several upper bounds on the total domination number in terms of the minimum degree, diameter, girth and order.

No description available.

No description available.

The concept of \emph{proper connection number} of graphs is an extension of proper colouring and is motivated by rainbow connection number of graphs. Let $G$ be an edge-coloured graph. Andrews et al.\cite{Andrews2016} and, independently, Borozan et al.\cite{Borozan2012} introduced the concept of proper connection number as follows: A coloured path $P$ in an edge-coloured graph $G$ is called a \emph{properly coloured path} or more simple \emph{proper path} if two any consecutive edges receive different colours. An edge-coloured graph $G$ is called a \emph{properly connected graph} if every pair of vertices is connected by a proper path. The \emph{proper connection number}, denoted by $pc(G)$, of a connected graph $G$ is the smallest number of colours that are needed in order to make $G$ properly connected. Let $k\geq2$ be an integer. If every two vertices of an edge-coloured graph $G$ are connected by at least $k$ proper paths, then $G$ is said to be a \emph{properly $k$-connected graph}. The \emph{proper $k$-connection number} $pc_k(G)$, introduced by Borozan et al. \cite{Borozan2012}, is the smallest number of colours that are needed in order to make $G$ a properly $k$-connected graph. The aims of this dissertation are to study the proper connection number and the proper 2-connection number of several classes of connected graphs. All the main results are contained in Chapter 4, Chapter 5 and Chapter 6. Since every 2-connected graph has proper connection number at most 3 by Borozan et al. \cite{Borozan2012} and the proper connection number of a connected graph $G$ equals 1 if and only if $G$ is a complete graph by the authors in \cite{Andrews2016, Borozan2012}, our motivation is to characterize 2-connected graphs which have proper connection number 2. First of all, we disprove Conjecture 3 in \cite{Borozan2012} by constructing classes of 2-connected graphs with minimum degree $\delta(G)\geq3$ that have proper connection number 3. Furthermore, we study sufficient conditions in terms of the ratio between the minimum degree and the order of a 2-connected graph $G$ implying that $G$ has proper connection number 2. These results are presented in Chapter 4 of the dissertation. In Chapter 5, we study proper connection number at most 2 of connected graphs in the terms of connectivity and forbidden induced subgraphs $S_{i,j,k}$, where $i,j,k$ are three integers and $0\leq i\leq j\leq k$ (where $S_{i,j,k}$ is the graph consisting of three paths with $i,j$ and $k$ edges having an end-vertex in common). Recently, there are not so many results on the proper $k$-connection number $pc_k(G)$, where $k\geq2$ is an integer. Hence, in Chapter 6, we consider the proper 2-connection number of several classes of connected graphs. We prove a new upper bound for $pc_2(G)$ and determine several classes of connected graphs satisfying $pc_2(G)=2$. Among these are all graphs satisfying the Chv\'tal and Erd\'{o}s condition ($\alpha({G})\leq\kappa(G)$ with two exceptions). We also study the relationship between proper 2-connection number $pc_2(G)$ and proper connection number $pc(G)$ of the Cartesian product of two nontrivial connected graphs. In the last chapter of the dissertation, we propose some open problems of the proper connection number and the proper 2-connection number.