Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 4 of 4
Full-Text Articles in Entire DC Network
A Few Problems On The Steiner Distance And Crossing Number Of Graphs, Josiah Reiswig
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, sdiamk(G), and the Steiner k-radius, sradk(G). In 1990, Henning, Oellermann and Swart [Ars Combinatoria 12 13-19, (1990)] showed that for any connected graph G, sdiam3(G) ≤(8/5)srad3(G) and …
On The Characteristic Polynomial Of A Hypergraph, Gregory J. Clark
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
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.
Quick Trips: On The Oriented Diameter Of Graphs, Garner Paul Cochran
Quick Trips: On The Oriented Diameter Of Graphs, Garner Paul Cochran
Theses and Dissertations
In this dissertation, I will discuss two results on the oriented diameter of graphs with certain properties. In the first problem, I studied the oriented diameter of a graph G. Erdos et al. in 1989 showed that for any graph with |V | = n and δ(G) = δ the maximum the diameter could possibly be was 3 n/ δ+1. I considered whether there exists an orientation on a given graph with |G| = n and δ(G) = δ that has a small diameter. Bau and Dankelmann (2015) showed that there is an orientation of diameter 11 n/ δ+1 + …