The purpose of this thesis is to investigate the graph isomorphism problem for a special class of graphs. Each graph is characterized by its edge set, and a subgroup of its automorphism group, called the colour group. In particular, a simple, efficient algorithm for determining whether two graphs are isomorphic if at least one is a member of the class is developed. Chapter 1 provides some basic definitions and lemmas required in the text. The concepts of reducibility and reducible bipartite graphs are introduced, and the properties of the colour groups of such graphs are investigated. Chapter 2 establishes some results concerning the existence of reducible graphs. Conditions based on the existence of vertices with prescribed properties are shown to provide sufficient conditions for a graph to be reducible. In the special case of trees they are shown to be both necessary and sufficient. Necessary conditions for the reducibility of graphs, based on their radius and diameter are also established. Chapter 3 describes an algorithm for determining whether a graph is completely reducible, which is applied to a test for isomorphism. An investigation of the speed of this algorithm is made and its efficiency is compared with an algorithm of D. Corneil [5], which this author considers the best for arbitrary graphs in the current literature. / Science, Faculty of / Computer Science, Department of / Graduate

No description available.

No description available.

The well studied class of irredundant vertex sets of a graph has been previously shown to be a special case of (a) a “Private Neighbor Cube” of eight classes of vertex subsets and (b) a family of sixty four classes of “generalised irredundant sets.” The thesis makes various advances in the theory of irredundance. More specifically: (i) Nordhaus-Gaddum results for all the sixty-four classes of generalised irredundant sets are obtained. (ii) Sharp lower bounds involving order and maximum degree are attained for two specific classes in the Private Neighbor Cube. (iii) A new framework which includes both of the above generalisations and various concepts of domination, is proposed. / Graduate

No description available.

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

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

Thesis (M.S.)--The University of North Carolina at Greensboro, 2008. / Directed by Paul Duvall; submitted to the Dept. of Mathematical Sciences. Title from PDF t.p. (viewed Sep. 4, 2009). Includes bibliographical references (p. 57).

Thesis (M.S.)--West Virginia University, 2005. / Title from document title page. Document formatted into pages; contains v, 17 p. : ill. Includes abstract. Includes bibliographical references (p. 17).

Ph.D. / In this thesis, our primary objective is to investigate the effects that various graph modifications have on the total domination number of a graph. In Chapter 1, we introduce basic graph theory concepts and preliminary definitions. In Chapters 2 and 3, we investigate the graph modification of edge removal. In Chapter 2, we characterize graphs for which the removal of any arbitrary edge increases the total domination number. We also begin the investigation of graphs for which the removal of any arbitrary edge has no effect on the total domination number. In Chapter 3, we continue this investigation and determine the minimum number of edges required for these graphs. The contents of Chapters 2 and 3 have been published in Discrete Applied Mathematics [15] and [16]. In Chapter 4, we investigate the graph modification of edge addition. In particular, we focus our attention on graphs for which adding an edge between any pair of nonadjacent vertices has no effect on the total domination number. We characterize these graphs, determine a sharp upper bound on their total domination number and determine which combinations of order and total domination number are attainable. 10 11 We also study claw-free graphs which have this property. The contents of this chapter were published in Discrete Mathematics [20]. In Chapter 5, we investigate the graph modification of vertex removal. We characterize graphs for which the removal of any vertex changes the total domination number and find sharp upper and lower bounds on the total domination number of these graphs. We also characterize graphs for which the removal of an arbitrary vertex has no effect on the total domination number and we further show that they have no forbidden subgraphs. The contents of this chapter were published in Discrete Applied Mathematics [14]. In Chapters 6 and 7, we investigate the graph modification of edge lifting. In Chapter 6, we show that there are no trees for which every possible edge lift decreases the domination number, and we characterize trees for which every possible edge lift increases the domination number. The contents of Chapter 6 were published in the journal Quaestiones Mathematicae [17]. In Chapter 7, we show that there are no trees for which every possible edge lift decreases the total domination number and that there are no trees for which every possible edge lift leaves the total domination number unchanged. We characterize trees for which every possible edge lift increases the total domination number. At the time of the writing of this thesis, the contents of Chapter 7 have been published online in the Journal of Combinatorial Optimization [18] and will appear in print in a future issue.