Skip to main content
edited tags
Link
YCor
  • 63.9k
  • 5
  • 187
  • 286
Source Link

Connected graphs $G$ with $\delta(G) > 1$ and long minimum size roundtrips

Let $G = (V,E)$ be a finite, connected, simple, undirected graph. By a roundtrip of $G$ we mean a map $r:\{0,\ldots,n\} \to V$ for some $n\in\mathbb{N}$ with the following properties:

  1. $r$ is surjective,
  2. $\{r(k), r(k+1)\} \in E$ for all $k \in \{0, \ldots, n-1\}$, and
  3. $r(0) = r(n)$.

The integer $n$ is called the length of the roundtrip $r$. An easy inductive argument shows that we can select $n$ such that $n \leq 2|V(G)|$. Let $\rho(G)$ denote the minimum length of any roundtrip in $G$.

For $k \geq 1$ let ${\frak r}(k)$ the maximum $\rho(G)$ where $G = (V,E)$ is a connected graph with $|V| =k$ and $G$ has no vertex of degree $1$. We have ${\frak r}(k) \leq 2k$ for all positive integers $k$.

Question. What is $$\lim\sup_{k\to\infty}\frac{{\frak r}(k)}{k}?$$

(Note: I ask for $\lim\sup$ instead of $\lim$ because while I am quite certain that the limit exists, I haven't been able to prove it.)