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

Summer 2019

## Document Type

Open Access Dissertation

Mathematics

Éva Czabarka

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, 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 conjectured that for all k ≥ 2 and a connected graph G, sdiamk(G) ≤ (2(k+1))/(2k−1)sradk(G). The paper also included an incorrect proof that sdiam4(G) ≤ (10/7)srad4(G). We provide a correct proof that sdiam4(G) ≤ (10/7)srad4(G) and show that for k ≥ 5, sdiamk(G) ≤ (k+3)/(k+1)sradk(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(2n/n), the Steiner k-diameter of the n-cube is k + Θ((2n)/√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 << n2, Pach, Spencer, and Tóth [Discrete and Computational Geometry 24 623-644, (2000)] showed that κ(n, e)(n2)/(e3) 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.