Physical Sciences and Mathematics Commons^™

A Few Problems On The Steiner Distance And Crossing Number Of Graphs, Josiah Reiswig

Theses and Dissertations

We provide a brief overview of the Steiner ratio problem in its original Euclidean context and briefly discuss the problem in other metric spaces. We then review literature in Steiner distance problems in general graphs as well as in trees.

Given a connected graph G we examine the relationship between the Steiner k-diameter, sdiam_k(G), and the Steiner k-radius, srad_k(G). In 1990, Henning, Oellermann and Swart [Ars Combinatoria 12 13-19, (1990)] showed that for any connected graph G, sdiam₃(G) ≤(8/5)srad₃(G) and …

On The Characteristic Polynomial Of A Hypergraph, Gregory J. Clark

Theses and Dissertations

We consider the computation of the adjacency characteristic polynomial of a uniform hypergraph. Computing the aforementioned polynomial is intractable, in general; however, we present two mechanisms for computing partial information about the spectrum of a hypergraph as well as a methodology (and in particular, an algo- rithm) for combining this information to determine complete information about said spectrum. The first mechanism is a generalization of the Harary-Sachs Theorem for hypergraphs which yields an explicit formula for each coefficient of the characteristic polynomial of a hypergraph as a weighted sum over a special family of its subgraphs. The second is a …

Kings In The Direct Product Of Digraphs, Morgan Norge

Theses and Dissertations

A k-king in a digraph D is a vertex that can reach every other vertex in D by a directed path of length at most k. A king is a vertex that is a k-king for some k. We will look at kings in the direct product of digraphs and characterize a relationship between kings in the product and kings in the factors. This is a continuation of a project in which a similar characterization is found for the cartesian product of digraphs, the strong product of digraphs, and the lexicographic product of digraphs.