2
$\begingroup$

Definitions. A tournament is an oriented complete graph, that is, it's what you get by taking a (finite or infinite) complete graph and assigning a unique direction to each edge. If $T$ is a tournament, $V(T)$ is its set of vertices and $E(T)$ its set of (directed) edges. If $u,v$ are vertices of a tournament (or digraph for that matter), the distance $d(u,v)$ is the minimum length of a (directed) path from $u$ to $v$, so $d(u,u)=0$; we put $d(u,v)=\infty$ if there is no path from $u$ to $v$. The eccentricity of a vertex $u$ of a tournament $T$ is $e(u)=\sup\{d(u,v):v\in V(T)\}$.

Motivation. It is a common exercise in graph theory to show that every finite tournament has a vertex of eccentricity at most two. (In fact, an arbitrary tournament $T$ contains either a vertex $u$ with $e(u)\le2$ or else an infinite sequence of vertices $v_1,v_2,\dots,v_n,\dots$ such that $v_jv_i\in E(T)$ whenever $i\lt j$.) Thus the following problem is only of interest for infinite tournaments.

Problem 1. Show that, if a tournament has a vertex of finite eccentricity, then it has a vertex of eccentricity at most three.

Problem 2. Find a tournament in which the eccentricity of every vertex is exactly three.

Context. These problems occurred to me after considering this question about finite tournaments. They are rather easy but I found them amusing, maybe you will too.

$\endgroup$
  • $\begingroup$ Looks like no one is interested in answering these silly questions, so I have to answer them myself. :-( $\endgroup$ – bof Mar 20 at 8:09
0
$\begingroup$

Problem 1. Show that, if a tournament has a vertex of finite eccentricity, then it has a vertex of eccentricity at most three.

Solution. Let $u$ be a vertex with $e(u)=n\lt\infty$, and suppose $n\gt3$. Choose a vertex $w$ with $d(u,w)=n$. Now consider any vertex $v$. If $d(u,v)\le n-2$ then $d(w,v)=1$; if $d(u,v)=n-1$ then $d(w,v)\le2$; and if $d(u,v)=n$ then $d(w,v)\le2$. Hence $e(u)\le3$.

By the way, for a simple example of a strongly connected tournament with no vertex of finite eccentricity, take $V(T)=\mathbb N$ and $E(T)=\{(u,v):v=u+1\text{ or }v\lt u-1\}$.


Problem 2. Find a tournament in which the eccentricity of every vertex is exactly three.

Solution. Let $V(T)=\mathbb N$ and $E(T)=\{(u,v):v\equiv u+1\pmod3\}\cup\{(u,v): v\equiv u\pmod3,\ v\lt u\}$. Then $e(u)=d(u,u+3)=3$ for every vertex $u$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.