الفهرس Only 14 pages are availabe for public view
 |  | from | 137 |  |  |
| | | from | 137 | | |
Abstract
Domination of Cartesian products of graphs and Vizing’s conjecture has been the field of study for a large number of authors since 1960s. One main intent of this research is to present a self–contained comprehensive study on this subject. For this purpose, the first chapter is dedicated to the required background. Most definitions and basic concepts in graph theory which will be assumed throughout this thesis are presented in section 1.1. Dominating sets in graphs are discussed in section 1.2. While in section 1.3 some examples, showing that dominating sets appear naturally in our life, are given. 1.1 Terminology and Basic Concepts First, some basic definitions, which can be found in [2] or any elementary book of graph theory, are given. A graph G = (V(G), E(G)) consists of a finite nonempty set denoted by V(G), or by V if the graph G under consideration is clear, and a collection E(G), or E, of unordered pairs {u, v} of distinct elements from V. Each element of V(G) is referred to as a vertex, and V(G) itself is called the vertex set of G. The members of the edge set E(G) are called edges. The cardinality of any set S, denoted by |S|, is the number of elements in S. For the graph G, the order of G is |V(G)|, and the size of G is |E(G)|. Sometimes, for simplicity, |G| will be used instead of |V(G)|. The edge e = {u, v} is said to join the vertices u and v. If e = {u, v} is an edge of a graph G, then u and v are adjacent vertices, while u and e are incident, as are v and e. Furthermore, if e1 and e2 are distinct edges of G incident with a common vertex, then e1 and e2 are adjacent edges. It is convenient to, henceforth, denote an edge by uv or vu rather than e = {u, v}. The degree, deg(v), of a vertex v in G is the number of edges incident with v in G. The minimum and maximum degrees of vertices in G are denoted by d(G) and D(G), respectively. If d(G) = D(G) = r, then G is said to be a regular graph of degree r, or simply r–regular graph.