## Date of Award

Summer 2019

## Document Type

Open Access Dissertation

## Department

Mathematics

## First Advisor

Éva Czabarka

## Second Advisor

László Székely

## Abstract

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_{3}(*G*) ≤(8/5)srad_{3}(*G*) and conjectured that for all k ≥ 2 and a connected graph *G*, sdiam_{k}(*G*) ≤ (2(k+1))/(2k−1)srad_{k}(*G*). The paper also included an incorrect proof that sdiam_{4}(*G*) ≤ (10/7)srad_{4}(*G*). We provide a correct proof that sdiam_{4}(G) ≤ (10/7)srad_{4}(*G*) and show that for k ≥ 5, sdiam_{k}(*G*) ≤ (k+3)/(k+1)srad_{k}(*G*). By construction, we also show that the latter of these bounds is tight for each k ≥ 5.

We then examine the Steiner distance of large sets in hypercubes. In particular, we show that for *k* = *O*(2^{n}/*n*), the Steiner *k*-diameter of the* n*-cube is k + Θ((2^{n})/√n) using a recent result of Griggs. This section is a joint work with Éva Czabarka and László Székely.

Finally, we move to structural properties of graphs in the context of crossing numbers. For positive integers* n* and *e*, let κ(*n*, *e*) be the minimum number of crossings among all graphs with* n* vertices and at least *e* edges. Under the condition that* n* << *e* << *n*^{2}, Pach, Spencer, and Tóth [*Discrete and Computational Geometry*** 24** 623-644, (2000)] showed that κ(*n*, *e*)(*n*^{2})/(*e*^{3}) tends towards a positive constant (called the midrange crossing constant) as *n* → ∞. We extend their proof to show that the midrange crossing constant exists for graph classes that satisfy a certain set of graph properties. As a corollary, we show that the the midrange crossing constant exists for the family of bipartite graphs. This section is a joint work with Éva Czabarka, László Székely, and Zhiyu Wang.

## Rights

© 2019, Josiah Reiswig

## Recommended Citation

Reiswig, J.(2019). *A Few Problems on the Steiner Distance and Crossing Number of Graphs.* (Doctoral dissertation). Retrieved from https://scholarcommons.sc.edu/etd/5386