A dominating set in a graph is a set S of vertices such that every vertex not in S is adjacent to a member S. A global defensive alliance in a graph is a dominating set S with the property that every vertex in S has in its closed neighborhood at least as many vertices in S as in V -- S. A global offensive alliance in a graph is a dominating set S with the property that every vertex in V -- S has in its closed neighborhood at least as many vertices in S as in V -- S. / We first study alliances in graphs. There are many results in this area. For example, it is known that every connected n-vertex graph G has a global offensive alliance of size at most 2n/3. Another result is that any global defensive alliance in G has size at least ( 4n+1 - 1)/2. Our study focuses particularly on trees and algorithms for finding alliances in trees. We find the cardinality of a minimum global offensive alliance for complete k-ary trees and the minimum cardinality global defensive alliance for complete binary and ternary trees. Also, we present a linear time algorithm for finding the minimum global offensive alliance in a tree. Additionally, for a general graph, an upper bound is given on the size of a minimum global offensive alliance in terms its degree sequence. The methods that we use in this part of the thesis are mainly algorithmic and deterministic. / Then we study independent dominating sets in graphs. An independent dominating set is a set of mutually nonadjacent vertices which is also a dominating set. This is a well-studied topic (see Haynes, Hedetniemi and Slater [22]). Our main result is to show that every d-regular graph of order n with girth at least 5 and satisfying d = o(1) and d2(log d)3/2 = o(n) contains an independent dominating set of size at most (1 + o(1)) nlogdd . This generalizes the results of Duckworth and Wormald [15] for random regular graphs. We construct the independent dominating set using recent probabilistic methods which resemble Rodl's semi-random method (see for example Alon and Spencer [1]).
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.116070 |
| Date | January 2008 |
| Creators | Harutyunyan, Ararat. |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Master of Science (Department of Mathematics and Statistics.) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | alephsysno: 002842094, proquestno: AAIMR67009, Theses scanned by UMI/ProQuest. |
Page generated in 0.0015 seconds