Spelling suggestions: "subject:"graph theory."" "subject:"raph theory.""
31 |
On the isomorphism problem for a class of bipartite graphsDixon, Anthony H. January 1970 (has links)
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
|
32 |
Probabilistic methods and domination related problems in graphsHarutyunyan, Ararat. January 2008 (has links)
No description available.
|
33 |
Finding a hamiltonian cycle in the square of a blockLau, H. T. (Hang Tong), 1952- January 1980 (has links)
No description available.
|
34 |
Generalisations of irredundance in graphsFinbow, Stephen 13 April 2017 (has links)
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
|
35 |
The strong chromatic index of cubic Halin graphsTam, Wing Ka 01 January 2003 (has links)
No description available.
|
36 |
Hamiltonian line graphs and claw-free graphsYan, Huiya. January 1900 (has links)
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).
|
37 |
Claw-free graphs and line graphsShao, Yehong, January 1900 (has links)
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).
|
38 |
On the Reconstruction conjectureWall, Nicole Turpin. January 1900 (has links)
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).
|
39 |
On the s-hamiltonian index of a graphShao, Yehong, January 1900 (has links)
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).
|
40 |
Total domination in graphs and graph modificationsDesormeaux, Wyatt Jules 20 August 2012 (has links)
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.
|
Page generated in 0.0603 seconds