Digital Commons Network^™

Sandwich Theorem And Calculation Of The Theta Function For Several Graphs, Marcia Ling Riddle

Theses and Dissertations

This paper includes some basic ideas about the computation of a function theta(G), the theta number of a graph G, which is known as the Lovasz number of G. theta(G^c) lies between two hard-to-compute graph numbers omega(G), the size of the largest lique in a graph G, and chi(G), the minimum number of colors need to properly color the vertices of G. Lovasz and Grotschel called this the "Sandwich Theorem". Donald E. Knuth gives four additional definitions of theta, theta_1, theta_2, theta_3, theta_4 and proves that they are all equal.

First I am going to describe the proof of the …

Evaluating The Performance Of Multiple Classifier Systems: A Matrix Algebra Representation Of Boolean Fusion Rules, Justin M. Hill

Theses and Dissertations

Given a finite collection of classifiers one might wish to combine, or fuse, the classifiers in hopes that the multiple classifier system (MCS) will perform better than the individuals. One method of fusing classifiers is to combine their final decision using Boolean rules (e.g., a logical OR, AND, or a majority vote of the classifiers in the system). An established method for evaluating a classifier is measuring some aspect of its Receiver Operating Characteristic (ROC) curve, which graphs the trade-off between the conditional probabilities of detection and false alarm. This work presents a unique method of estimating the performance of …

Bounding The Number Of Graphs Containing Very Long Induced Paths, Steven Kay Butler

Theses and Dissertations

Induced graphs are used to describe the structure of a graph, one such type of induced graph that has been studied are long paths.

In this thesis we show a way to represent such graphs in terms of an array with two colors and a labeled graph. Using this representation and the techniques of Polya counting we will then be able to get upper and lower bounds for graphs containing a long path as an induced subgraph.

In particular, if we let P(n,k) be the number of graphs on n+k vertices which contains P_n, a path on n vertices, as …