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]).

No description available.

The subject of the thesis belongs to the theory of graphs. In 1966, C. St. J.A. Nash-Williams conjectured that the square of a block is hamiltonian. This conjecture quickly gained a wide popularity and, at the end of 1970, it was established by H. Fleischner. His proof of the existence of a hamiltonian cycle in the square of a block does not explicitly provide an algorithm for finding the cycle. The thesis will describe such an algorithm, with a running time O(n('2)) on every input with n vertices. For the most part, our algorithm follows closely the original lines of Fleischner's proof. The main difference occurs at the part where Fleischner proves the existence of a certain spanning subgraph in every connected bridgeless graph: we replace Fleischner's argument by a radically different one. This is the main original result of our thesis.

<p>In this thesis only Binary codes are studied. Firstly, the codes overs the field GF(2) by the adjacency matrix of the complement T(n), ofthe triangular graph, are examined. It is shown that the code obtained is the full space F2 s(n/2) when n= 0 (mod 4) and the dual code of the space generated by the j-vector when n= 2(mod 4). The codes from the other two cases are less trivial: when n=1 (mod 4) the code is [(n 2), (n 2 ) - n + 1, 3] code, and when n = 3 (mod 4) it is an [(n 2), (n 2) - n, 4 ] code.</p>

<p>In this thesis only Binary codes are studied. Firstly, the codes overs the field GF(2) by the adjacency matrix of the complement T(n), ofthe triangular graph, are examined. It is shown that the code obtained is the full space F2 s(n/2) when n= 0 (mod 4) and the dual code of the space generated by the j-vector when n= 2(mod 4). The codes from the other two cases are less trivial: when n=1 (mod 4) the code is [(n 2), (n 2 ) - n + 1, 3] code, and when n = 3 (mod 4) it is an [(n 2), (n 2) - n, 4 ] code.</p>

Thesis (Ph. D.)--Ohio University, August, 1982. / Title from PDF t.p.

Thesis (Ph.D.) -- University of Rhode Island, 2007 / Typescript. Includes bibliographical references (leaf 99).

Thesis (Ph. D.)--West Virginia University, 1999. / Title from document title page. Document formatted into pages; contains vii, 69 p. : ill. Includes abstract. Includes bibliographical references (p. 67-69).

Thesis--London. / Includes bibliographical references.

Thesis (Ph. D.)--West Virginia University, 2004. / Title from document title page. Document formatted into pages; contains vi, 53 p. : ill. Includes abstract. Includes bibliographical references (p. 48-53).