\begin{document}

\parindent=0cm

\title{The average solution of a TSP instance in a graph}

\begin{abstract}
    We define the average $k$-TSP distance $\mutspk$ of a graph $G$ as the average length of a shortest walk visiting $k$ vertices, i.e. the expected length of the solution for a random TSP instance with $k$ uniformly random chosen vertices. We prove relations with the average $k$-Steiner distance and characterize the cases where equality occurs. We also give sharp bounds for $\mutspk(G)$ given the order of the graph.
\end{abstract}

\section{Introduction}\label{sec:intro}

 

For a set of $k$ vertices, a Steiner-tree in a graph $G$ is a subtree of $G$ of minimum order which contains the $k$ vertices.
A Steiner-tree for the set of all vertices of a graph is a spanning tree, so the Steiner-tree problem is a generalization of the spanning tree problem.
In $1989$, Chartrand et al.~\cite{COT89} defined the Steiner distance $d_k(v_1,v_2, \ldots, v_k)$ of a k-tuple of vertices $(v_1,\ldots, v_k)$ as the size of a minimum connected subgraph (subtree) which contains all vertices. This lead to the notion of the average Steiner distance, defined in~\cite{DOS96}, and the Steiner-Wiener index, defined in~\cite{LMG16}.
Surveys on Steiner distance and related Steiner distance parameters can be found in~\cite{Oellermannsurvey,MaoSurvey}.
The notion Steiner tree does exist for digraphs as well and so one could define the average Steiner $k$-distance as the average over all ordered $k$-tuples $(v_1,v_2,\ldots, v_k)$ of the minimum size of a Steiner tree connecting the root $v_1$ with all terminal vertices $v_2, \ldots, v_{k-1}$ and $ v_k.$
Algorithms to determine the smallest Steiner tree in this setting have been investigated as well, see e.g.~\cite{Guo90}.
For our purpose, we prefer to define the Steiner distance $d_k(v_1,v_2, \ldots, v_k)$ in a digraph as the minimum number of arcs in a biconnected subdigraph containing the vertices $(v_i)_{1 \le i \le k},$ which is the analogue of the definition used by Chartrand et al.~\cite{COT89}.
Now the average Steiner distance is just the average over all $k$-tuples, and the Steiner-Wiener index $W_k(D)$ of a digraph the sum over all $k$-tuples of vertices.

The travelling salesman problem (TSP for short) asks for a shortest walk (for definitions, see Subsection~\ref{subsec:def&not}) in a graph that contains a given set of vertices. This problem can also be considered for (weighted) digraphs.
It is an important problem in operations research and computer science. For more information, see e.g.~\cite{GP02}. Variants of both the TSP and Steiner-tree problem are often NP-hard, but are somewhat easier for restricted graph classes, see e.g.~\cite{MPP18}.
In this paper we will look to some theoretical averaging questions.
The TSP problem has been studied in many directions, but a pure mathematical study of the extremal behaviour of the problem seems lacking.

We define the analogue of Steiner distance and Steiner-Wiener index for the TSP problem; the average $k$-TSP distance and $k$-TSP-Wiener index.
The analogues of certain other distance measures such as e.g. eccentricity, diameter and radius for TSP can be defined as well, done here in Subsection~\ref{subsec:def&not} for completeness.

\begin{definition}
    In a graph $G$, for $k$ vertices $v_1,v_2, \ldots, v_k$ we define the $k$-TSP distance\\ $\tsp_k(v_1,v_2, \ldots, v_k)$ as the length of a shortest closed walk that visits all vertices $v_1,v_2, \ldots, v_k$.\\
    The $k$-TSP-Wiener index of a graph $G$ is defined as 
    $$\Wtspk(G)= \sum_{\binom{V}{k}} \tsp_k(v_1,v_2, \ldots, v_k).$$\\
    The $k$-average TSP-distance equals 
    $$\mutspk(G)=\frac{\Wtspk(G)}{\binom{n}{k}}.$$

\end{definition}

The $k$-TSP-Wiener index of a digraph can be defined compeletely similar as in the graph case.

\begin{definition}
    In a digraph $D$, we define $\tsp_k(v_1,v_2, \ldots, v_k)$ as the length of a shortest closed walk in $D$ that visits all vertices $v_1,v_2, \ldots, v_k$.\\
    The $k$-TSP-Wiener index of a digraph $D$ is defined as 
    $$\Wtspk(D)= \sum_{\binom{V}{k}} \tsp_k(v_1,v_2, \ldots, v_k).$$\\
    The $k$-average TSP-distance equals 
    $$\mutspk(D)=\frac{\Wtspk(D)}{\binom{n}{k}}.$$
\end{definition}

In both cases, one can consider weighted versions, as is the case for TSP-instances as well.
In that case every edge or arc is assigned some weight and $\tsp_k(v_1,\ldots,v_k)$ denotes the minimum sum of weights over all closed walks visiting each of these vertices.
An asymmetric TSP has to be formulated with weights on the arcs of a digraph, where the arcs $\overrightarrow{uv}$ and $\overrightarrow{vu}$ do not necessarily get the same weight. 

Both the TSP-Wiener index and Steiner-Wiener index for $k=2$ reduce to the usual Wiener index.
When $k=3$, it was proven in~\cite[cor.~4.5]{LMG16} that for trees $W_3(T)=\frac{n-2}{2} W(T)$. Nevertheless this is not true for all graphs, while we will note that $\Wtsp3(G)=(n-2)W(G)$ is true for all graphs $G$ and so in some sense this variant behaves nicer.
As a main result, we characterize the graphs for which certain TSP-Wiener indices and Steiner-Wiener indices are equal up to exactly a factor $2.$

\begin{theorem}\label{thr:TSPW=2W}
    For a graph $G$ and integer $k\ge 2$, we have $\Wtspk(G)\le 2\W_k(G).$
    Equality does hold if and only if $k=2$, $k=3$ and $G$ contains no vertices $u,v,w$ for which $2\max\{d(u,v),d(u,w),d(v,w)\}<d(u,v)+d(u,w)+d(v,w)$ and every choice of $3$ shortest paths between the $3$ pairs $(u,v),(v,w), (w,u)$ are edge-disjoint, or $k \ge 4$ and $G$ is a tree.
\end{theorem}

This is proven in Section~\ref{sec:rel_Wk_Wtspk}.
In Section~\ref{sec:bounds_mutspk} we prove the sharp lower- and upper bound for the average $k$-TSP distance, and characterize the extremal graphs.

\begin{theorem}
    For every $k \ge 2$ and graph $G$ of order $n$, $$k \le \mutspk(G) \le 2\frac{k-1}{k+1}(n+1),$$
\end{theorem}

Finally, we also consider the analogue of the DeLaVi\~{n}a-Waller~\cite{DLVW} conjecture, which states that the cycle $C_{2d+1}$ attains the maximum average distance among all graphs with diameter $d$ and order $n=2d+1,$ for every $d \ge 3.$
We prove that this extension is false for $k \ge 4$.

\subsection{Definitions and Notation}\label{subsec:def&not}

A walk in a graph $G=(V,E)$ is a sequence of vertices $(v_1,v_2, \ldots, v_r)$ such that $v_iv_{i+1}\in E$ for every $1\le i \le r-1.$ It is a closed walk if $v_1=v_r.$ A path is a walk in which all vertices are distinct.  
The distance $d(u,v)$ between two vertices $u$ and $v$ equals the length of a shortest path containing them.
The total distance or Wiener-index $W(G)$ is the sum of all distances.

A walk in a digraph $D=(V,A)$ is defined similarly, it is a sequence of vertices $(v_1,v_2, \ldots, v_r)$ such that $\overrightarrow{v_iv_{i+1}}\in A$ for every $1\le i \le r-1.$
It is a closed walk if $v_1=v_r,$ and it is a (directed) path if all vertices are distinct.

Let $n$ and $k$ be integers such that $2 \le k \le n$ and let $G$ be a graph of order $n.$
The TSP-$k$-eccentricity of a vertex $v$ of $G$ equals $\ecc_{tsp,k}(G,v)=\ecc_{tsp,k}(v)= \max\{\tsp_k(S) \mid S\subset V, \abs{S}=k,  v \in S\}.$
The TSP-$k$-radius and TSP-$k$-diameter of a vertex $v$ of $G$ are defined by $\rad_{tsp,k}(G)=\min\{\ecc_{tsp,k}(v) \mid v \in V\}$ and $\diam_{tsp,k}(G)=\max\{\ecc_{tsp,k}(v) \mid v \in V\}$.

\section{Relations between the Steiner-Wiener and TSP-Wiener index}\label{sec:rel_Wk_Wtspk}

In this section, we prove Theorem~\ref{thr:TSPW=2W}, hereby starting with the inequality itself.

\begin{proposition}\label{prop:TSPWle2W}
    For a graph $G$ and integer $k\ge 2$, we have $\Wtspk(G)\le 2\W_k(G).$ 
\end{proposition}

\begin{proof}
    Given a minimum Steiner-tree spanning $k$ vertices $v_1, v_2, \ldots, v_k,$ one can make a walk along this Steiner-tree visiting every edge precisely twice. The latter follows from induction on the size of a tree and taking a cut-vertex in the induction step.
    This implies that $\tsp_k(v_1, v_2, \ldots, v_k) \le 2d(v_1, v_2, \ldots, v_k).$ Summing over $\binom{V}{k},$ we obtain the result.
\end{proof}

The characterization of the graphs that attain equality is harder, except from the case $k=2$. When $k=2,$ a shortest walk visiting $v_1$ and $v_2$ will always have length $2d(v_1,v_2).$
Before going on with the characterization for $k \ge 3$, we prove the following theorem relating the $k$-TSP-Wiener index with the Wiener index.

\begin{theorem}\label{thr:wtspk_vs_W}
    For every graph $G$ of order $n \ge k$, we have 
    $\Wtspk(G) \le k \binom{n}{k}\mu(G)= \frac{2}{k-1} \binom{n-2}{k-2} W(G).$
    Equality does hold if and only if $k \in \{2,3\}$, or $k>3$ and $G$ equals $S_n$ or $K_n$.
\end{theorem}

\begin{proof}
    Once the order $(v_1,v_2, \ldots, v_k)$ of vertices  visited in the walk is determined, we have 
    $\tsp_k(v_1,v_2, \ldots, v_k)=d(v_1,v_2)+d(v_2,v_3)+\ldots+d(v_{k-1},v_k)+d(v_k,v_1).$
    Let $\,\mathbb{E} \sum_{i=1}^k d(v_i,v_{i+1})$ be the average over all $k!$ possible permutations of the $k$ vertices (where we take $v_{k+1}=v_1$ in the sum).
    Then $\tsp_k(v_1,v_2, \ldots, v_k) \le \,\mathbb{E} \sum_{i=1}^k d(v_i,v_{i+1})$
    and thus 
    \begin{align*}
        \Wtspk(G)&\le \sum_{(v_i)_{1 \le i \le k} \in \binom{V}{k}}  \,\mathbb{E} \sum_{i=1}^k d(v_i,v_{i+1})\\
        &= k \binom{n}{k}\mu(G).
    \end{align*}
    For $k \in \{2,3\},$ every permutation results in the same sum and so the equality is true for every graph.
    
    For $K_n$, we trivially have $\Wtspk(K_n)=k\binom{n}{k}$ and for a star one easily verifies that
    $$\Wtspk(S_n)=2k \binom{n-1}{k}+ 2(k-1) \binom{n-1}{k-1} = \frac{2k(n-1)}{n}\binom{n}{k}=k \binom{n}{k}\mu(S_n).$$
    
    Now assume that $n \ge k \ge 4$ and $G$ is not a clique nor a star. This implies that $G$ has a spanning tree which is not a star and in particular that $G$ contains two disjoint edges (this is also a consequence of Erd\H{o}s-Ko-Rado results).
    
    Equality did only occur if all permutations gave the same sum, so in particular for every $4$ vertices $v_1,v_2,v_3,v_4$ we have $d(v_1,v_2)+d(v_2,v_3)+d(v_3,v_4)=d(v_1,v_3)+d(v_2,v_3)+d(v_2,v_4),$ which is equivalent with $d(v_1,v_2)+d(v_3,v_4)=d(v_1,v_3)+d(v_2,v_4).$
    By the same argument, the latter also equals $d(v_1,v_4)+d(v_2,v_3).$
    So any two disjoint edges span a $K_4$.
    In particular $G$ contains a $K_4$. Let $K_m$ be a largest clique in $G$, and let $(v_i)_{1 \le i \le m}$ be its vertices.
    Since $G$ is not a clique itself and connected, there is a vertex $u$ adjacent to some vertices of the clique, e.g. $v_1$, but not all of them, e.g. $v_3$.
    Since $uv_1$ and $v_2v_3$ are disjoint edges in $G$, they span a $K_4$ and so $uv_3 \in E(G)$, which is a contradiction with our choice of $u$. From this we conclude.
\end{proof}

    As such, for $k=3,$ we have $\Wtsp3(G)=(n-2)W(G)$ for every graph $G$.
    The characterization of the graphs for which $2W_3(G)=\Wtsp3(G)$ can now be formulated and proven as follows. 
    As such, we give here an alternative proof for the inequality $2W_3(G)\ge \Wtsp3(G)$ (which the reader may skip).
    
\begin{theorem}
    Every graph $G$ satisfies $W_3(G) \ge \frac{n-2}{2} W(G).$
    Equality does hold if and only if $G$ contains no vertices $u,v,w$ for which $2\max\{d(u,v),d(u,w),d(v,w)\}<d(u,v)+d(u,w)+d(v,w)$ and every choice of $3$ shortest paths between the $3$ pairs $(u,v),(v,w), (w,u)$ are edge-disjoint.
    
    
    
\end{theorem}
\begin{proof}
    By definition, $d_3(u,v,w)$ is the number of edges in a minimum tree $T$ spanning $u,v$ and $w$.
    Either this tree is path, in which case $d_3(u,v,w)=\frac 12 \left(d(u,v)+d(v,w)+d(v,w)\right),$ or it has a single vertex of degree $3$, call it $z$.
    In the latter case, we have $d(u,v) \le d(u,z)+d(z,v)$ by the triangle inequality and the two analogues of this.
    Hence \begin{equation}\label{eq:triangle-ineq}
        d_3(u,v,w)=d(u,z)+d(v,z)+d(w,z) \ge \frac 12 \left(d(u,v)+d(v,w)+d(v,w)\right).
    \end{equation}
    So the latter equality is true for all triples.
    Summing over all triples in $\binom{V}{3},$ every distance $d(u,v)$ appears $n-2$ times, from which we conclude that $W_3(G) \ge \frac{n-2}{2} W(G).$
    
    If equality does hold in Inequality~\eqref{eq:triangle-ineq} for every triple of vertices $(u,v,w)$, either their Steiner-tree is a path and thus $2\max\{d(u,v),d(u,w),d(v,w)\}=d(u,v)+d(u,w)+d(v,w)$, or the $3$ shortest paths between the $3$ pairs $(u,v),(v,w), (w,u)$ can be chosen such that each of them contains $2$ of the $3$ branches of the tree and as such are not edge-disjoint.
    
    Now we prove the other direction.
    Let $(u,v,w)$ be a triple of vertices in $G$ for which inequality~\eqref{eq:triangle-ineq} is strict.
    We can always choose the shortest paths between the pairs in $\{u,v,w\}$ such that their union forms a pseudotree (unicyclic graph or tree). Choose these in such a way that the cycle is as small as possible (not a tree by choice of $(u,v,w)$). This is sketched in Figure~\ref{fig:shortestpaths}.
    \begin{figure}
\caption{Sketch of shortest paths between the three vertices $(u,v,w)$ }
\label{fig:shortestpaths}
\end{figure}

    Let $(u',v',w')$ be the three vertices with degree $3$ in this unicyclic graph.
    If there would exist a choice of shortest paths between these $3$ vertices that are not internally vertex-disjoint/ edge-disjoint, this would imply that we had a choice with a smaller cycle, which would be a contradiction. So they are edge-disjoint.
    Also $2\max\{d(u',v'),d(u',w'),d(v',w')\}<d(u',v')+d(u',w')+d(v',w')$ due to the triangle-inequality and the assumption that the shortest paths between them were edge-disjoint.
    \end{proof}
  

\begin{remark}
 Examples of graphs for which the equality $W_3(G) = \frac{n-2}{2} W(G)$ does hold are graphs all of whose induced cycles are $C_4$s (e.g. complete bipartite graphs) and convex subsets of the $n$-dimensional gridgraph.
 Non-bipartite graphs (consider a smallest odd cycle) and bipartite graphs containing an induced $C_6$ (consider the $3$ vertices of the $C_6$ in the same bipartition class) are examples of graphs for which no equality does hold.
\end{remark}
\begin{comment}
        We can always choose the shortest paths between the pairs in $\{u,v,w\}$ such that their union forms a unicyclic graph. Choose these in such a way that the cycle is as small as possible (or a tree whenever possible).
    If the length is at least $5$, it is not induced and we can find induced $C_4$s in the corners, there is a contradiction as the cycle would not have been the smallest one. 
    This is sketched in Figure~\ref{fig:shortestpaths}. The shortest cycle can be reduced with two, by letting it be the shortest cycle through $v',u_2,u_1,w'$ instead of $v',u',w'.$
    
    \begin{figure}
\caption{Sketch of shortest paths between the three vertices}
\label{fig:shortestpaths}
\end{figure}
     If the length of the cycle is four, we note that we could have chosen a tree as the union of the shortest paths.
\end{comment}

\begin{comment}
    If $G$ contains an odd cycle, take a smallest odd cycle $C_m=(v_0,v_1, \ldots, v_{m-1})$ of $G$.
    Then for every $0 \le i,j \le m-1$, we have $d_{G}(v_i,v_j)=d_{C_m}(v_i,v_j),$ as otherwise $G$ would contain a smaller odd cycle.
    This implies that for $(u,v,w)=(v_0, v_{\floorfrac m3}, v_{\floorfrac{2m}3})$, we have $d(u,v)+d(v,w)+d(v,w)=m \neq 2d_3(u,v,w).$
    So inequality~\eqref{eq:triangle-ineq} would not be true for this triple.
    Hence a graph $G$ for which $W_3(G) = \frac{n-2}{2} W(G)$ needs to be bipartite.
    
    E.g.: If $G$ contains a $K_3$ spanned by vertices $u,v$ and $w$, then \\ $d_3(u,v,w)=2>\frac 12 \left(d(u,v)+d(v,w)+d(v,w)\right)$ and so Inequality~\eqref{eq:triangle-ineq} is not an equality for all triples of vertices.
\end{comment}

Finally, we prove the characterization of the extremal graphs in Theorem~\ref{thr:TSPW=2W} for $k \ge 4.$

\begin{proposition}\label{thr:TSPW=2W_tree}
    For a tree $T$ and integer $k\ge 4$, we have $\Wtspk(T)=2\W_k(T).$
    If $G$ is a graph that is not a tree, then $\Wtspk(G)<2\W_k(G).$
\end{proposition}

\begin{proof}
    Since the vertices visited in a shortest walk on a tree, form a tree itself and every edge is used exactly twice, we have $\tsp_k(v_1,v_2, \ldots, v_k)=2d_k(v_1,v_2, \ldots, v_k)$ for every $k$-tuple, by summing over $\binom{V}k$ we conclude that $\Wtspk(T)=2\W_k(T).$
    
    Now assume $G$ is not a tree and it has girth $m$, i.e. there is a smallest cycle $C_m$ belonging to $G$.
    If $k \le m,$ one can distribute the points over the cycle in such a way that they do not belong to an interval of length smaller than $\frac m2$ (here we use $k \ge 4$).
    Since the cycle is chosen minimal, this also implies that a minimum Steiner-tree will contain at least $\frac {m+1}{2}$ edges. Hence $2d_k(v_1,v_2, \ldots, v_k)\ge m+1.$
    On the other hand one can walk along $C_m$, i.e. put the vertices in the other of the cycle, and thus $\tsp_k(v_1,v_2, \ldots, v_k)\le m.$
    
    If $k>m$, one can take a set of $k$ vertices $v_1$ up to $v_k$, containing the $m$ on the cycle and $k-m$ others.
    Take a minimum Steiner-tree $T'$ containing these $k$ vertices which contains the largest number of edges of the cycle $C_m.$
    If there are less than $m-2$ edges of the cycle contained in $T'$, consider two neighbours $u$ and $v$ in $C_m$ that are not connected by edges in $E(C_m) \cap E(T').$
    Since $u,v \in T'$, there is a path connecting them which is partially outside $C_m$. Let $xy \in E(T')\backslash E(C_m)$ be an edge on this path.
    Note that $T'=T"\backslash xy \cup uv$ is a new Steiner-tree for the $k$ vertices, for which 
    $\lvert E(C_m) \cap E(T")\rvert > \lvert E(C_m) \cap E(T')\rvert.$
    Contradiction. So we can assume $T'$ contains all edges from $C_m$ except from one, which we call $uv$.
    Now one can do a walk from $v$ to $u$ which visits all vertices of $T'$.
    Then all edges from $T'$ will be traversed twice, except from $E(C_m) \cap E(T')$ which are only traversed once.
    Now ending with the edge $uv$, we conclude that (since $m \ge 3$) that $\tsp_k(v_1,v_2, \ldots, v_k)<2d(v_1,v_2, \ldots, v_k).$
\end{proof}

We also prove a relation between the Steiner-Wiener and TSP-Wiener index for digraphs.

\begin{proposition}\label{prop:TSPWle2W}
    For a digraph $D$ and integer $k\ge 2$, we have $\Wtspk(D)\ge \W_k(D).$ 
\end{proposition}

\begin{proof}
    Let $\{v_1,\ldots,v_k\}$ be a set with $k$ vertices. 
    Take a closed walk in $D$ visiting these $k$ vertices. This results in a biconnected digraph, i.e. the vertices and arcs visited in the walk form a biconnected digraph.
    This implies that $d(v_1,\ldots,v_k) \le \tsp_k(v_1,\ldots,v_k).$ Summing over all possible $k$-vertex sets in $\binom{V}{k}$, one concludes that $\Wtspk(D)\ge \W_k(D).$ 
\end{proof}

In contrast to Theorem~\ref{thr:TSPW=2W}, the relation between $\Wtspk(D)$ and $\W_k(D)$ already depends on the digraph when $k=2.$
For this, consider the digraph $DP_{n,d}$, which is the directed cycle $\overrightarrow{C_d}$ with a blow-up of one vertex by an independent set $\{\ell_1,\ell_2,\ldots,\ell_{n-d+1}\}$ of size $n -d + 1$, presented in Figure~\ref{fig:DPnd} (or~\cite[Fig.3]{SC19}).
We note that the shortest walk reaching both $\ell_1$ and $\ell_{2}$ will have length $2d$, while the minimum number of arcs in a biconnected digraph containing both $\ell_1$ and $\ell_{2}$ is $d+2.$ For this digraph, one can observe that when $n>>d>>k$, the ratio between $d_k(\ell_1,\ell_2, \ldots, d_k) = d-2+2k$ and $\tsp_k(\ell_1,\ell_2, \ldots, d_k)=dk$ is roughly $k$ and 
$\Wtspk(D)\sim k \W_k(D),$ while $\Wtspk(D)\le k \W_k(D)$ is a trivial upper bound since 
$d(v_1, \ldots, v_k) \ge \max\{d(v_i,v_j) \mid 1 \le i,j \le k\}+1$ and $\tsp_k(v_1, \ldots, v_k) \le k \cdot \max\{d(v_i,v_j) \mid 1 \le i,j \le k\}.$

\begin{figure}
\caption{The digraph $DP_{n,d}
\label{fig:DPnd}
\end{figure}

\section{Bounds on the average TSP-distance}\label{sec:bounds_mutspk}

\begin{theorem}
    For every $k \ge 2$ and graph $G$ of order $n$, $$k \le \mutspk(G) \le 2\frac{k-1}{k+1}(n+1),$$
    or equivalently
    $$\Wtspk(K_n) \le \Wtspk(G) \le \Wtspk(P_n).$$
    Equality for the upper bound does hold if and only if $G$ is the path $P_n$, or $k=n$ and $G$ is a tree.
    The lower bound is true if and only if every $k$ vertices in $G$ span a $C_k$, i.e. form a Hamiltonian subset.
\end{theorem}

\begin{proof}
    The lower bound is immediate, since $\tsp_k(v_1,v_2,\ldots,v_k) \ge k$ for every $k$-set of vertices.
    Equality does hold if and only if $G[v_1,v_2,\ldots,v_k]$ contains a spanning cycle, i.e. $G[v_1,v_2,\ldots,v_k]$ is Hamiltonian, for every $k$-set $\{v_1,v_2,\ldots,v_k\} \subset V.$
    
    The upper bound is true by combining Theorem~\ref{thr:TSPW=2W} and~\cite[Thr.~3]{LMG16}, as together they imply that $\Wtspk(G) \le 2 W_k(G) \le 2 W_k(P_n)=\Wtspk(P_n).$
    Equality does hold if and $\Wtspk(G) = W_k(G)$ and $\mu_k(G)=\frac{k-1}{k+1}(n+1),$ which is when $G=P_n$ or $k=n$ and $G$ is a tree, by combining Theorem~\ref{thr:TSPW=2W} and~\cite[Thr.~2.1]{DOS96}. Here we note that if $k=n=2,$ $P_2$ is the only graph on $2$ vertices and when $k=3$ $\mutsp3(K_3)<\mutsp3(P_3).$
\end{proof}

\begin{remark}
    For $k \in \{2,3\},$ the clique $K_n$ is the unique graph attaining the minimum. This is also a corollary of the result for the average distance and Theorem~\ref{thr:wtspk_vs_W}.
    For $k \ge 4,$ the condition $\delta(G) \ge n+2-k$ is necessary to ensure that $\delta(G[v_1,v_2,\ldots,v_k])\ge 2$ for every $k$-tuple, but this is only sufficient when $k \le 5.$
\end{remark}

\begin{remark}
    The analogue of~\cite[Thr.~2.2]{DOS96} does also hold for the average TSP-distance for both graphs and digraphs. 
    That is, if $D$ be a biconnected, weighted digraph and $2 \le j, k$ be integers with $j+k-1 \le n.$ Then $\mu_{tsp,j+k-1}(D) \le  \mutspk(D) + \mu_{tsp,j}(D).$
    The underlying reason being that the union of two closed walks with a vertex in common, can be combined in a closed walk whose (weighted) length is the sum of the other two.
\end{remark}

Knowing the extremal bounds for graphs of order $n$, without any constraint, it is natural to wonder about the extremal values and graphs for certain logical constraints.
One of these is the diameter $d$ of the graph.
Plesn\'{\i}k~\cite{P84} asked these questions for the average distance, and it turned out that determining the maximum average distance given order and diameter is a very hard question. The best estimations known at this point can be found in~\cite{SC19}.
One beautiful conjecture related to the problem of Plesn\'{\i}k is the one by DeLaVi\~{n}a and Waller~\cite{DLVW}. Here they conjecture that when the order equals $2d+1$ and the diameter $d$ is at least $3$, then the cycle $C_{2d+1}$ maximizes the average distance.
As a corollary of Theorem~\ref{thr:wtspk_vs_W}, we observe that the DeLaVi\~{n}a-Waller conjecture is true for the TSP-Wiener index of order $k$ for $k \in \{2,3\}$ if and only if the original version is true.
In the remaining of this section, we will show that the analogue would not go through for the TSP-variant of the problem when $k \ge 4.$ The essence is that $\mutspk(C_n) \le n$, while for a tree with order $n$ we may have $\mutspk(T) \sim 2n$ when $k$ is reasonably large.

Before proving this, we estimate $\mutspk(C_n).$

\begin{lemma}\label{lem:Cn_mutspk}
        For $k$ fixed and $n$ sufficiently large, we have 
        $$\mutspk(C_n) \sim \left(1-\frac{1}{2^{k-1}} \right) n.$$
\end{lemma}
    \begin{proof}
        Let $d=\floorfrac{n}{2}.$
        Note that if $k$ vertices $v_1\ldots v_k$ do not belong to an interval of length at most $d$, then $\tsp_k(v_1,\ldots,v_k)=n.$
        If they do belong to an interval of length $i \le d$, then $\tsp_k(v_1,\ldots,v_k)=2i.$
        
     As such, we can compute that 
     \begin{align*}
         \Wtspk(C_n)&= n \sum_{i=k}^d \binom{i-2}{k-2}\cdot 2\cdot (i-1) + \left( \binom{n}{k} - n\sum_{i=k}^d \binom{i-2}{k-2}\right)n\\
         &= 2n(k-1) \sum_{i=k}^d \binom{i-1}{k-1} + \left( \binom{n}{k} - n \binom{d-1}{k-1}\right)n\\
         &= 2n(k-1) \binom{d}{k} + \left( \binom{n}{k} - n \binom{d-1}{k-1}\right)n\\
         &\sim 2n(k-1) \frac{1}{2^k} \binom{n}{k} + n\binom{n}{k} -nk \frac{1}{2^{k-1}} \binom{n}{k}\\
         &=  \binom{n}{k} \left( 1 - \frac{1}{2^{k-1}}\right)n
     \end{align*}
     
     Here we used that $\sum_{i=a}^b \binom{i}{a} = \binom{b+1}{a+1}$, which can be proven by induction, as well as $\binom{n}{k}=\frac nk \binom{n-1}{k-1}$ and $\binom{n}k \sim 2^k \binom dk$ when $d>>k.$
    \end{proof}

In the next theorem, we prove that the tree presented in Figure~\ref{fig:tree_beatingC_2d+1_wtspk} has a larger $k$-TSP-Wiener index for any $k \ge 4,$ when $n$ (equivalently $d$) is sufficiently large.

\begin{figure}
\caption{A symmetric tree with order $2d+1$ and diameter $d$ with large $\mutspk(T)$}
\label{fig:tree_beatingC_2d+1_wtspk}
\end{figure}

\begin{theorem}
    When $k \ge 4$ and $d$ is sufficiently large, there do exist trees with diameter $d$ and order $n=2d+1$ for which $\mutspk(C_{n})<\mutspk(T).$

\end{theorem}

\begin{proof}
    Take the tree $T$ which consists of a central vertex of degree $3$ which is connected to $3$ brooms of length roughly $\frac d2$ and with roughly $\frac d6$ leaves each, in such a way that the order is $2d+1$ and the diameter equals $d.$ 
    The shortest walk containing $k$ vertices, will contain an edge $e=uv$ twice if and only if among the $k$ vertices, there are vertices closer to $u$ than to $v$ and also in the reverse order.
    If $e$ is an edge such that $T \backslash e$ has two components with $a$ resp. $b$ vertices (so $a+b$=n), then the probability that the $k$ vertices are in the same component is $\frac{\binom{a}{k}+\binom{b}{k}}{\binom{n}{k}}.$
    When $a$ and $b$ are much larger than $k$, this is approximately $\frac{a^k+b^k}{(a+b)^k}$
    As such, the expected value for $\mutspk(T)$ is roughly (3 paths and every edge in the walk has to be traversed twice)
 \begin{align*}
    6 \cdot \sum_{a=\frac d6}^{\frac{2d}{3}}\left(1- \frac{ a^k + (2d-a)^k}{(2d)^k} \right) & \sim 6\cdot \int_{ a=\frac d{6}}^{\frac{2d}3} \left(1- \frac{ a^k + (2d-a)^k}{(2d)^k} \right) \d a\\
     & \sim 6\cdot \int_{ \frac 1{12}}^{\frac13} \left( 1-x^k-(1-x)^k \right) \d x \cdot 2d
 \end{align*}
    When $k \ge 6,$ this is larger than $2d+1>\mutspk(C_{n})$ for $d$ sufficiently large.
    For $k=5$, it is larger than $1.98d$ and for $k=4$ it is larger than $1.752 d$.
    On the other hand, by Lemma~\ref{lem:Cn_mutspk} we have $\mutspk(C_n) \sim \left(2-\frac{1}{2^{k-2}} \right) d,$ which is smaller than the two values for the tree when $k \in \{4,5\}.$
\end{proof}

\section{Conclusion and further directions}\label{sec:conc}

In this paper, we defined the average TSP-distance of a graph and digraph, as well as a version for the Steiner distance for digraphs.
We compared and investigated the extremal behaviour of average TSP-distance and average Steiner distance.
While solving a general TSP instance precisely is a hard problem, the study of the average TSP-distance, e.g. for random graphs or certain graph classes, may give some fundamental insights on the travelling salesman problem. 
Also certain problems for other distance measures, such as TSP-$k$-radius might be interesting.
The latter is related to the worst solution of a TSP-instance with $k-1$ destinations and an  optimally chosen base location.

A few observations are immediate for the eccentricities (and the same is true for the radius and diameter analogues).
For a tree $T$, $\ecc_{tsp,k}$ equals $2\ecc_k$.
If $H$ is a spanning subgraph of $G$, then $\ecc_{tsp,k}(G,v)\le \ecc_{tsp,k}(H,v)$.
By starting from a clique and deleting one edge belonging to a triangle at a time till one ends with a path, for $k \ge 3$ one can observe that given the order, $\ecc_{tsp,k}(v)$ can take any value between $k$ and $2(n-1)$. 
It would be interesting to see more surprising behaviour/ results that gives additional intuition on TSP-instances. 

\begin{comment}
This implies that both $\rad_{tsp,k}(G)$ and $\diam_{tsp,k}(G)$ can take any value between $k$ and $2(n-1)$ (when $k \ge 3$) as well.  
Also $\rad_{tsp,k}(G)\le \rad_{tsp,k}(H)$ and $\diam_{tsp,k}(G)\le \diam_{tsp,k}(H)$.

Some questions may be in close relation with its Steiner version, e.g.~\cite{ADM12}.
\end{comment}

\end{document}