A Few Problems on the Steiner Distance and Crossing Number of Graphs

Author

Josiah Reiswig

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₃(G) ≤(8/5)srad₃(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₄(G) ≤ (10/7)srad₄(G). We provide a correct proof that sdiam₄(G) ≤ (10/7)srad₄(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), the Steiner k-diameter of the n-cube is k + Θ((2ⁿ)/√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², Pach, Spencer, and Tóth [Discrete and Computational Geometry 24 623-644, (2000)] showed that κ(n, e)(n²)/(e³) 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