The maximum Wiener index of a uniform hypergraph

The Wiener index [16], also known as the total distance, is a well-studied parameter in graph theory. For a given graph $G$, the Wiener index of the graph is denoted by $W(G)$ where

$$W(G)=\sum_{\{u,v\}\subseteq V(G)}d_{G}(u,v).$$

The Wiener index of a graph with a fixed number of vertices is linearly related to the average distance of the graph, which is itself another important metric parameter in random graph theory. Additionally, it is related to parameters of random walks such as cover cost and Kemeny’s constant [8, 12]. Its generalization of Steiner-Wiener index [13] is related to the average traveling salesman problem distance [5].

It is natural to investigate the extremal properties of the Wiener index. Among the most basic results on the total distance of a graph, there are folklore results that for every connected graph $G$ and a tree $T$ with $n$ vertices, we have

$$W(K_{n})\leq W(G)\leq W(P_{n})\mbox{~{}and~{}}W(S_{n})\leq W(T)\leq W(P_{n}).$$

Here $K_{n}$ is the $n$-vertex complete graph, $P_{n}$ is a path with $n$ vertices and $S_{n}$ is a star with $n$ vertices. Proofs can be found in [4].

While these statements and proofs might be straightforward and easy, the relationship between the Wiener index and other graph parameters or specific classes of graphs is still being explored. For example among all graphs with a given diameter and order the minimum Wiener index is determined in [15]. In [3] the maximum Wiener index is determined up to the asymptotics of the second-order term. The authors in [6, 7, 9] have studied planar graphs and determined sharp bounds for the maximum of the Wiener index in Apollonian planar graphs and maximal planar graphs.

In this work, we study the Wiener index of $k$-uniform hypergraphs. Generalizing fundamental results in graph theory to hypergraphs gives a broader insight into the problem. A few examples of such extensions of classical results towards the hypergraph setting are given in [14, 11]. A $k$-uniform hypergraph $\mathcal{H}$ of order $n$ can be represented as a pair $(V,E)$ where $V$ is a vertex set with $n$ elements and $E\subseteq\binom{V}{k}$ is a family of $k$-sets, called hyperedges or just edges. Note that in the case of $k=2$, a $2$-uniform hypergraph is a graph. In order to introduce a distance between the vertices of a hypergraph, at first we need to introduce a concept of paths for hypergraphs. In this work we follow the celebrated definition of Berge [1]: a Berge path of a hypergraph $\mathcal{H}$ is a sequence of distinct vertices and hyperedges $v_{0}h_{1}v_{1}h_{2}v_{2}\ldots v_{d-1}h_{d}v_{d}$ of $\mathcal{H}$ where $v_{i-1},v_{i}\in h_{i}$ for every $1\leq i\leq d$ for some $d$. A hypergraph is connected if there is a Berge path for every pair of vertices. The length of a Berge path is the number of hyperedges in the Berge path. Naturally the distance between two vertices $u,v$ is the length of the shortest Berge path containing $u$ and $v$ in the hypergraph $\mathcal{H}$, and it is denoted by $d_{\mathcal{H}}(u,v)$. Note that when the ground hypergraph is known from the context we write $d(u,v)$ instead of $d_{\mathcal{H}}(u,v)$. The Wiener index of a connected hypergraph $\mathcal{H}$ is defined as $\sum_{\{u,v\}\subseteq V(\mathcal{H})}d_{\mathcal{H}}(u,v).$

A connected hypergraph $\mathcal{H}$ is called a hyper-tree when it can be represented by a tree $T$ in the graph sense, on the same vertex set, where every edge of $\mathcal{H}$ induces a connected subgraph of $T$, equivalent formulations are collected in [2, Chap. 5, Sec. 4]. When restricting to linear $k$-uniform hyper-trees (connected hypergraphs with $n=m(k-1)+1$ vertices and $m$ edges), it was shown in [10] that for every such hyper-tree $\mathcal{H}$, $W(S_{n}^{k})\leq W(\mathcal{H})\leq W(P_{n}^{k})$, where $S_{n}^{k}$ and $P_{n}^{k}$ are the linear path and star, see Figure 1. Furthermore, the corresponding extremal hyper-trees are unique.

Considering arbitrary connected $k$-uniform hypergraphs, or hyper-trees, the extremal hypergraphs for maximizing/minimizing the Wiener index are not always unique. Determining the lower bound for the Wiener index of $k$-uniform hypergraphs is trivial, as all distances between the distinct vertices are at least $1$.

We remark that, in huge contrast with the graph case, equality can also be attained by very sparse hypergraphs.

On the other hand, maximizing the Wiener index for $k$-uniform hypergraphs is a relatively complex problem. In this note, we determine the maximum possible Wiener index of a connected $n$-vertex $k$-uniform hypergraph and characterize all hypergraphs attaining the maximum. First, we define the class of extremal hypergraphs. For integers $a$ and $b$ with $a\leq b$, let $[a,b]$ be the set $\{a,a+1,\ldots,b\}$ and $[a]$ be the set $[1,a]$. For given integers $n$ and $k$ with $0\leq k<n$, let $s$ and $r$ be integers such that $n=ks+r$ and $0\leq r<k$. For every $r$ such that $r\neq 0$, let $P_{n}^{k}=(V,E)$ be the following tight-path. Let the vertex set of $P_{n}^{k}$ be $[n]$ and the edge set be $E=\left\{[(i-1)k+1,ik]\colon 1\leq i\leq s\right\}\cup\left\{[r+(i-1)k+1,ik+r]\colon 1\leq i\leq s\right\}.$ For $r=0$, and every integer $x$, such that $0<x<k$, we define a $k$-uniform hypergraph $P_{n,x}^{k}=(V,E)$ where $V=[n]$ and $E=\{[(i-1)k+1,ik]\colon 1\leq i\leq s\}\cup\{[(i-1)k+1+x,ik+x]\colon 1\leq i\leq s-1\}.$ See Figure 2 for examples of both $P_{n}^{k}$ and $P_{n,x}^{k}$. Our main result can now be stated as follows.

Let $\mathcal{H}=(V,E)$ be an $n$-vertex $k$-uniform connected hypergraph with maximum Wiener index. Then we may assume that for every edge $h$ of $\mathcal{H}$, the hypergraph $\mathcal{H}^{\prime}=(V,E\backslash h)$¹¹1We abuse notation and write $E\backslash h$ instead of $E\backslash\{h\}$. is not connected, otherwise we would remove the edge and the Wiener index would not decrease. Proving Theorem 1 for edge-minimal hypergraphs is sufficient since adding an edge to one of the extremal hypergraphs from Theorem 1 decreases the Wiener index. The following lemma shows that there is a hyperedge $h$ in $E$, such that hypergraph $\mathcal{H}^{\prime}=(V,E\backslash h)$ an contains at most one connected component of size greater than one.

By Lemma 3 and the edge-minimality of $\mathcal{H}$, there is an edge $h_{1}$ of $\mathcal{H}$ such that $\mathcal{H}^{\prime}=(V,E\backslash h_{1})$ consists of a connected component of order $n-\ell$ on a vertex set $V^{\prime}\subset V$ and $\ell$ isolated vertices for some $1\leq\ell<k$. Let $\mathcal{H}^{\prime}_{V^{\prime}}$ be the largest connected component of $\mathcal{H}^{\prime}$.

Now we proceed by induction, noting that the theorem trivially holds for $n<2k$. Assume Theorem 1 holds for every order strictly smaller than $n$. Let $v$ be an isolated vertex of $\mathcal{H}^{\prime}$ such that $\sum_{u\in V^{\prime}}d_{\mathcal{H}^{\prime}}(u,v)$ is the maximum possible. Then we have

$$W(\mathcal{H})\leq W(\mathcal{H}^{\prime}_{V^{\prime}})+\binom{\ell}{2}+\ell\sum_{u\in V^{\prime}}d(u,v).$$

(1)

By induction, we have an upper bound on $W(\mathcal{H}^{\prime}_{V^{\prime}}).$ For this, we compute the Wiener index of the paths $P_{n}^{k}$ and $P_{n,x}^{k}$. When $n=ks+r,$ for some integers $s$ and $r$ such that $0\leq r<k$, the Wiener index of the path equals

$\displaystyle f(s,k,r)$

$\displaystyle=\frac{k^{2}s^{3}}{3}+rks^{2}+r^{2}s+\frac{(k^{2}-3k)s}{6}+\binom{r}{2},$

Note that the Wiener index of $P_{n,x}^{k}$ is independent of the choice of $x$.

We also need to find an upper bound for $\sum_{u\in V^{\prime}}d_{\mathcal{H}}(u,v)$. To this end, we define the following two functions:

	$\displaystyle g_{1}(\ell,k,s,r)$	$\displaystyle=ks^{2}+\ell s+r(2s+1),$
	$\displaystyle g_{2}(\ell,k,s,r)$	$\displaystyle=ks^{2}+\ell s+2rs.$

Finally, it is sufficient to prove that the upper bound for the right-hand side of Inequality (1) is always bounded by the claimed upper bound. For $n-\ell=ks+r$, we have

	$\displaystyle f(s+1,k,r+\ell-k)$	$\displaystyle-\left(f(s,k,r)+\ell g_{1}(\ell,k,s,r)+\binom{\ell}{2}\right)=(k-\ell-r)^{2}\geq 0\>\>\mbox{ if }k-\ell\leq r,$
	$\displaystyle f(s,k,r+\ell)$	$\displaystyle-\left(f(s,k,r)+\ell g_{2}(\ell,k,s,r)+\binom{\ell}{2}\right)=\ell r\geq 0\>\>\>\quad\quad\quad\quad\mbox{ if }k-\ell>r,$

which also has been verified by Maple²²2See https://github.com/StijnCambie/WienerHypergraph.

Equality holds if $k=\ell+r$ or $r=0$. If $k\mid n,$ equality occurs if and only if $k=\ell+r$ and for every fixed $0<\ell<k$ the only hypergraph attaining the maximum Wiener index is $P_{n,\ell}^{k}$. If $k\nmid n,$ equality occurs if and only if $r=0$, since $0<\ell<k$ and by the induction hypothesis the unique connected $n$-vertex $k$-uniform hypergraph maximizing the Wiener index is $P_{n}^{k}$.