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

2 
Graph partitions and integer flowsChen, Xujin., 陳旭瑾. January 2004 (has links)
published_or_final_version / abstract / toc / Mathematics / Doctoral / Doctor of Philosophy

3 
Some results in graph theoryLaw, Kaho., 羅家豪. January 2010 (has links)
published_or_final_version / Mathematics / Doctoral / Doctor of Philosophy

4 
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>

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

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

7 
Graph minorNiu, Jianbing. January 1900 (has links)
Thesis (Ph. D.)West Virginia University, 2004. / Title from document title page. Document formatted into pages; contains vi, 55 p. Includes abstract. Includes bibliographical references (p. 5355).

8 
Small cycle cover, group coloring with related problemsLi, Xiangwen, January 1900 (has links)
Thesis (Ph. D.)West Virginia University, 2002. / Title from document title page. Document formatted into pages; contains vi, 120 p. : ill. Includes abstract. Includes bibliographical references (p. 114120).

9 
Dynamic coloring of graphsMontgomery, Bruce Lee. January 2001 (has links)
Thesis (Ph. D.)West Virginia University, 2001. / Title from document title page. Document formatted into pages; contains viii, 52 p. : ill. Vita. Includes abstract. Includes bibliographical references (p. 51).

10 
Chords of longest circuits of graphsLi, Xuechao. January 2001 (has links)
Thesis (Ph. D.)West Virginia University, 2001. / Title from document title page. Document formatted into pages; contains vi, 57 p. : ill. Includes abstract. Includes bibliographical references (p. 5657).

Page generated in 0.043 seconds