Spelling suggestions: "subject:"graph theory."" "subject:"raph theory.""
11 
Probabilistic methods and domination related problems in graphsHarutyunyan, Ararat. January 2008 (has links)
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 nvertex 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 kary 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 wellstudied topic (see Haynes, Hedetniemi and Slater [22]). Our main result is to show that every dregular 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 semirandom method (see for example Alon and Spencer [1]).

12 
Coloring girth restricted graphs on surfacesWalls, Barrett Hamilton 08 1900 (has links)
No description available.

13 
Finding a hamiltonian cycle in the square of a blockLau, H. T. (Hang Tong), 1952 January 1980 (has links)
The subject of the thesis belongs to the theory of graphs. In 1966, C. St. J.A. NashWilliams 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.

14 
Codes from uniform subset graphs and cycle products.Fish, Washiela. January 2007 (has links)
<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 jvector 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>

15 
Codes from uniform subset graphs and cycle products.Fish, Washiela. January 2007 (has links)
<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 jvector 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>

16 
On unique realizability of digraphs and graphsJameel, Muhammad. January 1982 (has links)
Thesis (Ph. D.)Ohio University, August, 1982. / Title from PDF t.p.

17 
On the ErdősSós conjecture /Tiner, Gary F. January 2007 (has links)
Thesis (Ph.D.)  University of Rhode Island, 2007 / Typescript. Includes bibliographical references (leaf 99).

18 
Broadcasting in grid graphsWojciechowska, Iwona. January 1999 (has links)
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. 6769).

19 
Some contributions to the theory of colour=critical graphsToft, Bjarne. January 1900 (has links)
ThesisLondon. / Includes bibliographical references.

20 
On flows of graphsXu, Rui, January 1900 (has links)
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. 4853).

Page generated in 0.0822 seconds