說明 
92 p 
附註 
Source: Dissertation Abstracts International, Volume: 6703, Section: B, page: 1468 

Adviser: Frederick C. Harris, Jr 

Thesis (Ph.D.)University of Nevada, Reno, 2006 

This dissertation addresses the generation of minimal complete graphs. A complete graph, denoted Kn, is a graph in which each vertex is connected to every other vertex of the graph with an edge. A minimal graph is a representation of a graph that exhibits its crossing number. The crossing number of a graph is the smallest number of edge crossings over all planar representations of the graph 

Presented is a constructive framework for iteratively generating minimal Kn from minimal Kn 1. The process described allows for complete enumeration of all minimal Kn derivable from minimal Kn1, including those graphs that are only locally minimal. A graph is locally minimal if it reflects the smallest number of crossings possible for a given region placement of vertex n in minimal Kn 1. All graphs are classified into isomorphic families, allowing for efficient iteration to the next set of complete graphs of order n + 1 due to needing only one representative from each K n isomorphic family for complete results 

In addition to determining the crossing number for Kn generated by Kn1, all minimal graphs are available for exploration of their underlying structure. This allows for substructure isomorphic analysis and localized region neighborhood analysis, both of which will lead to yet more efficient iteration of K n for increasing n. Information culled from these graphs may also shed light on new or improved lower bound estimation techniques 

A sevenstep process is presented that allows for iterative growth. The main module in the process, Star Analysis, takes a global view of growing minimal Kn by focusing on optimizing the enumeration of all star graphs, K1,n1, centered at vertex n placed into initial minimal K n1 at all possible different region locations 

This research introduces new conjectures and opens some new questions for exploring the structure of minimal Kn. Though this work focuses on minimal complete graphs, the process appears to be applicable to an assortment of other graph families. An example is presented of its application to complete bipartite graphs 

School code: 0139 

DDC 
Host Item 
Dissertation Abstracts International 6703B

主題 
Mathematics


0405

Alt Author 
University of Nevada, Reno

