Results on the Wiener profile

Peer review under responsibility of Kalasalingam University.

1 Introduction

Let $G=(V,E)$ be a simple connected graph (without loops and multiple edges). The distance $d(u,v)$ of two vertices $u,v\in V$ is the number of edges in a shortest path between $u$ and $v$. The Wiener index $w\left(G\right)$ of $G$ is the sum of these distances for all distinct pairs $d(u,v)$. This concept was introduced by Harry Wiener, who showed that this graph parameter is closely correlated with some chemical parameters, for instance with the boiling points of alkane molecules [1]. As an example, the Wiener indices of a large classes of fullerenes are determined in [2]. The book [3] contains many analogues and generalizations of the Wiener index, all of them have relevance in chemistry.

Let us introduce a new vector-parameter, the Wiener profile as the $n-1$-dimensional vector $(f_1,f_2,\dots ,f_{n-1})$ where $f_k$ is the number of pairs of distinct vertices $(u,v)$ with distance $d(u,v)=k$. It is easy to see that the Wiener index is equal to $w\left(G\right)=\sum _{i=1}^{n-1}i{f}_i.$The contribution of a pair $(u,v)$ of vertices (atoms in a molecule) to the Wiener index is $i$ if their distance is $d(u,v)=i$. However, if we want to have a parameter which indicates a certain chemical property then the contribution of a pair $(u,v)$ could be different from their distance. Suppose that it is some ${\alpha }_i$ in case when $d(u,v)=i$. Here we supposed that the contribution of the pair $(u,v)$ to the property depends only on their distance. But the choice of the numbers ${\alpha }_i$ might depend on the chemical property in question. Let $\alpha =({\alpha }_1,{\alpha }_2,\dots ,{\alpha }_{n-1})$ be the vector of these coefficients. Then the weighed Wiener index with these coefficients is $w_{\alpha }=\sum _{i=1}^{n-1}{\alpha }_i{f}_i.$The choice $\alpha =(1,2,\dots ,n-1)$ gives back the Wiener index.

We will study the structure of the set of Wiener profiles of graphs on $n$ vertices. Suppose e.g. that we want to find the molecule containing $n$ atoms and having a certain chemical property the most or least, then we have to maximize or minimize $w_{\alpha }$ under the condition that $(f_1,f_2,\dots ,f_{n-1})$ is the Wiener profile of a graph of $n$ vertices ($\alpha$ is fixed!). From the chemical point of view it makes sense only to consider connected graphs, but technically it is easier to handle the set of all graphs on $n$ vertices. If a graph is not connected disregard the pairs in different components. Take all Wiener profiles of the graphs on at most $n$ vertices (in other words the subgraphs of the $n$-vertex complete graph $K_n$.) Denote this set by ${\mathbb{W}}_n$. It is a set of points with integer coordinates in the $n-1$-dimensional Euclidean space.

Let us note that profile vectors were also studied in Extremal Set Theory (see e.g. [4]). There is, however a huge difference between the structures of the sets of profile vectors there and here. In Extremal Set Theory, if the coordinates of a profile vectors are decreased (remaining in the non-negative range) then the new vector is also a profile vector. This is not true here at all, as the $n=3$ shows. There are 4 non-isomorphic graphs on three vertices: the complete graph $K_3$, the path of two edges, a single edge and the empty graph. Their profiles in this order are $(3,3),(2,1),(1,0),(0,0)$. That is, ${\mathbb{W}}_3=\{(3,3),(2,1),(1,0),(0,0)\}$. One can see that $(3,2)$ is not a profile though $(3,3)$ is.

Our main task is to give necessary and/or sufficient conditions on vectors to make them Wiener profiles. There is one trivial condition. Since $f_i$ is counting the number of distances $i$, their sum counts the total number of distances. $\sum _{i=1}^{n-1}{f}_i=\left(\genfrac{}{}{0ex}{}{n}{2}\right).$But there are more complex relations among the coordinates $f_i$. We will introduce them below. However, before that, we suggest a new invariant of graphs that intuitively also has significance in chemistry. In the Wiener index and in the Wiener profile the pairs of vertices with distance $k$ are considered. The distance is defined by a shortest path between the two vertices. But there might be more paths of the same (shortest) length between the vertices. The molecule is probably more rigid if the vertices are connected with more paths. This motivation makes us to introduce the concept of the path profile. Let $p_k$ be the number of paths of length $k$ in the graph $G$ containing $n$ vertices $(1\le k<n)$. The path profile is the vector $(p_1,p_2,\dots ,p_{n-1})$. The path index is then $\pi \left(G\right)=\sum _{i=1}^{n-1}i{p}_i.$

Here we will call the attention on some more complex necessary conditions that $p_k$’s and $f_k$’s must satisfy. Suppose that $p_k$ is known, fixed. One can intuitively feel that $p_{k-1}$ cannot be too small. Indeed, the graph contains $p_k$ paths of length $k$, these paths contain many paths of length $k-1$. This fact must give a lower bound on the number $p_{k-1}$. Let us use a somewhat different approach, considering the set $E$ of edges. The $p_k$ paths are its $k$-element subsets. Deleting the first or last edge from such a path, a path of length $k-1$ is obtained. What is the minimum number of these $k-1$-element subsets? The literature knows a very closely related problem/results. Let $\mathcal{A}$ be a family of $k$-element sets. The shadow $\sigma \left(\mathcal{A}\right)$ is a family of those $k-1$-element sets which are obtained from the members of $\mathcal{A}$ deleting one (arbitrary) element. The Shadow Theorem [5,6] determines the exact minimum of $\left|\sigma \left(\mathcal{A}\right)\right|$ for given $k$ and $\left|\mathcal{A}\right|$ (where $\left|S\right|$ denotes the size of the set $S$). We will study an analogous problem here.

The Path Shadow Problem. Knowing the number $p_k$ of paths of length $k$ in a graph, determine (or estimate) the minimum number of subpaths of length $k-1$ (or in general of length $\ell$ ). There are substantial differences between this problem and the traditional Shadow Problem. Here the $k$-element subsets of edges are not necessarily paths of length $k$, in contrast to the case of the Shadow Problem. On the other hand, in the new problem we cannot delete edges arbitrarily from a path obtaining a shorter path.

The Distance Shadow Problem is formally very similar. Given $f_k$, the number of pairs of distinct vertices with distance $k$, determine the minimum number of distances $k-1$ in a graph. Our present paper is devoted to these two problems.

2 Minimization of path and distance shadows

Given a graph $G$ let $f_k=f_k\left(G\right)$ be the number of pairs of distinct vertices $(u,v)$ with distance $d(u,v)=k$. Our goal in this section is to find the minimum of $f_{\ell }\left(G\right)$ for all graphs containing $f_k$ pairs with distance $k$ where $k>\ell$. Denote the minimum by $M(f_k,k,\ell )$. If $n$, the number of vertices is known then we can define the minimum $M(f_k,n,k,\ell )$. These quantities are the minimum sizes of the distance shadow. The following inequality is obvious. (1) $M(f_k,k,\ell )\le M(f_k,n,k,\ell ).$(1)

But there is an another variant of this problem. The distance $d(u,v)$ is defined by a (shortest) path. In our modified problem we consider all paths of length $k$, not only the ones which define the distance. Let $N(f_k,k,\ell )$ denote the minimum number of paths of length $\ell$ in a graph containing exactly $f_k$ paths of length $k$. Similarly, let $N(f_k,n,k,\ell )$ denote the same under the condition that the number of vertices of the graph is fixed: $n$. The following inequality is obvious, again. (2) $N(f_k,k,\ell )\le N(f_k,n,k,\ell ).$(2) These are the minimum sizes of the path shadows.

2.1 The case $\ell =1$, paths

The results in this subsection are taken from the literature. We list them for the sake of completeness.

Here the number of distances 1 and the number of paths of length 1, that is the number of edges should be minimized in both cases. It is easier to handle the following inverse problem. The number of edges in the graph is given, determine the maximum number of distances $k$ or paths of length $k$ in the graph, either fixing the number of vertices or not.

Let the inverse of $N(f_k,k,1)$ be $R(e,k)$. This is the maximum number of paths of length $k$ in a graph containing $e$ edges. Similarly, let $R(n,e,k)$ denote the same under the condition that not only the number of edges, but also the number of vertices is given: $e$ and $n$, respectively. It is easy to determine $R(e,2)$.

Proposition 1

$R(e,2)=\left(\genfrac{}{}{0ex}{}{e}{2}\right).$

Proof

The star (one “central” vertex contained in all $e$ edges) gives the above value, proving $R(e,2)\ge \left(\genfrac{}{}{0ex}{}{e}{2}\right).$ On the other hand a path of length two consists of two edges, therefore one cannot have more of them than $\left(\genfrac{}{}{0ex}{}{e}{2}\right)$.  □

It is more difficult to determine $R(n,e,2)$. Paper [7] contains an almost complete solution. In order to be able to formulate its main statement some definitions are needed. A quasi-clique consists of a clique (complete graph) and an additional vertex adjacent to a subset of the vertices of the clique. (If there is no additional vertex then the quasi-clique is simply a clique.) A quasi-star is the complement of a quasi-clique.

Theorem 1

[7]

$R(n,e,2)$ is equal to the number of paths of length two either in a quasi-star or in a quasi-clique with $e$ edges. Moreover the extremal graph is a quasi-star if $e\le \frac{1}{2}\left(\genfrac{}{}{0ex}{}{n}{2}\right)-\frac{n}{2}$ and a quasi-clique if $e\ge \frac{1}{2}\left(\genfrac{}{}{0ex}{}{n}{2}\right)+\frac{n}{2}$.

One can see from this special case that the determination of $R(e,k)$ is easier than that of $R(n,e,k)$. However in the case of $k=3$ the difference is not so much.

Theorem 2

[8]

If $10\le \left(\genfrac{}{}{0ex}{}{a}{2}\right)\le e<\left(\genfrac{}{}{0ex}{}{a+1}{2}\right)$ holds then $R(e,3)\le 2e(e-a)\frac{a-2}{a}$ with equality for the complete graph on $a$ vertices.

Here we do not have the exact value for all $e$, but this theorem gives a very good asymptotic estimate for $R(e,3)$. Moreover, the best (asymptotic) construction does not depend on $n$. Therefore the asymptotic solution (that is sharp for infinitely many $e$) gives the asymptotically sharp solution for $R(n,e,3)$, too.

Based on these results one can guess that the odd and even $k$’s behave differently.

Theorem 3

[9], see also [8]

If $k$ is odd then both $R(n,e,k)$ and $R(e,k)$ are asymptotically equal to $2^{\frac{k-1}{2}}{e}^{\frac{k+1}{2}}$ and the asymptotically sharp construction is a complete graph.

Theorem 4

[8]

If $k$ is even then $R(e,k)$ is asymptotically equal to $c_k{e}^{\frac{k}{2}+1}$, where $c_k$ is a constant depending only on $k$.

If $k=4$, then $R(e,4)$ is basically known.

Theorem 5

[10]

If $e$ is large enough then $R(e,4)=\left\{\begin{array}{cc}\frac{e^3}{8}-\frac{3e^2}{4}+e\hfill & ifeiseven,\hfill \\ \frac{e^3}{8}-\frac{7e^2}{8}+\frac{15e}{8}-\frac{9}{8}\hfill & ifeisodd.\hfill \end{array}\right.$The extremal construction is a complete bipartite graph with sizes $\lfloor \frac{e}{2}\rfloor$ and 2.

Very little is known on $R(n,e,k)$, but $R(n,e,4)$ is asymptotically determined.

Theorem 6

[11]

$R(n,e,4)$ is asymptotically equal to the number of paths either in a quasi-star or in a quasi-click.

2.2 The case $\ell =1$, distances

We consider the inverse again. The inverse of $M(f_k,k,1)$ is $S(e,k)$: this the maximum number of distances $k$ in a graph with $e$ edges, while $S(n,e,k)$ is the maximum number of distances $k$ in a graph with $n$ vertices and $e$ edges. Of course (3) $S(e,k)\le R(e,k)\text{and}S(n,e,k)\le R(n,e,k)$(3) holds. The inequalities are usually very sharp, since, e.g. the number of distances is at most quadratic in $n$, while the number of paths can be much larger.

Proposition 2

$S(e,2)=\left(\genfrac{}{}{0ex}{}{e}{2}\right).$

Proof

The statement follows from Proposition 1, (3(3) $S(e,k)\le R(e,k)\text{and}S(n,e,k)\le R(n,e,k)$(3) ) and the fact that the star with $e$ rays contains this many distances 2.  □

Proposition 3

$S(n,e,2)=\left\{\begin{array}{cc}\left(\genfrac{}{}{0ex}{}{e}{2}\right)\hfill & \text{if}e\le n-1,\hfill \\ \left(\genfrac{}{}{0ex}{}{n}{2}\right)-e\hfill & \text{if}n\le e.\hfill \end{array}\right.$

Proof

If $e\le n-1$ then one cannot have more than $\left(\genfrac{}{}{0ex}{}{e}{2}\right)$ paths of length 2, therefore this is an upper bound for the number of distances, as well. The star of $e$ edges gives equality. On the other hand, if $n\le e$ then the distance between the endpoints of an edge is one, cannot be two. Hence the total number of distances two cannot be more than $\left(\genfrac{}{}{0ex}{}{n}{2}\right)-e$. The star with $n-1$ rays and $e-(n-1)$ other edges gives the equality.  □

Theorem 7

For fixed $k$ and large $e$ $S(e,k)$ is asymptotically equal to $\left(\genfrac{}{}{0ex}{}{e}{2}\right).$

Proof

Let us see that the number of finite distances in a graph with $e$ edges cannot exceed $\left(\genfrac{}{}{0ex}{}{e+1}{2}\right)$. If the graph is connected then the number of vertices is at most $e+1$, therefore the number of distances is at most $\left(\genfrac{}{}{0ex}{}{e+1}{2}\right)$. Suppose now that the numbers of edges in the $r$ components are $e_1,e_2,\dots ,e_r$ where $e_1+e_2+\cdots +e_r=e$. The $i$’s component has at most $e_i+1$ vertices therefore at most $\left(\genfrac{}{}{0ex}{}{e_i+1}{2}\right)$ edges. The total number edges is at most $\sum _{i=1}^r\left(\genfrac{}{}{0ex}{}{e_i+1}{2}\right).$This is really at most $\left(\genfrac{}{}{0ex}{}{e+1}{2}\right)$ as the following lines show: $\sum _{i=1}^r\left(\genfrac{}{}{0ex}{}{e_i+1}{2}\right)=\frac{1}{2}\sum _{i=1}^r{e}_i^2+\frac{1}{2}\sum _{i=1}^r{e}_i\le \frac{1}{2}{\left(\sum _{i=1}^r{e}_i\right)}^2+\frac{1}{2}\sum _{i=1}^r{e}_i=$ $\left(\genfrac{}{}{0ex}{}{\sum _{i=1}^r{e}_i+1}{2}\right)=\left(\genfrac{}{}{0ex}{}{e+1}{2}\right).$

Since $\left(\genfrac{}{}{0ex}{}{e+1}{2}\right)$ and $\left(\genfrac{}{}{0ex}{}{e}{2}\right)$ are asymptotically equal, the latter one is really an asymptotical upper bound.

Below we will construct asymptotically optimal graphs, distinguishing cases according to $k$.

Suppose first that $k$ is even. Let $T(t,k∕2)$ be a complete $t$-ary tree of depth $k$. This is a tree with a root of degree $t$, all other vertices have degrees $t+1$ and 1. The latter one are the leaves. The distance of the root and a leaf is $k∕2$. The number of edges is (4) $e=t+t^2+\cdots +t^{k∕2}=t\frac{t^{k∕2}-1}{t-1}\sim t^{k∕2}$(4) where it is supposed in the asymptotical calculation that $k$ is fixed and $t$ is large. Denote the vertices of distance 1 from the root by $v_1,\dots ,v_t$, while the set of leaves connected to the root through $v_i$ is denoted by $L_i$. It is easy to see that the distance of the vertices $a\in L_i$ and $b\in L_j(i\ne j)$ in the tree $T(t,k∕2)$ is exactly $k$. Of course $\left|L_i\right|=t^{k∕2-1}$. Hence the number of pairs of vertices with distance $k$ is at least (in fact exactly) $\left(\genfrac{}{}{0ex}{}{t}{2}\right){\left(t^{k∕2-1}\right)}^2\sim \frac{t^k}{2}.$Using (4(4) $e=t+t^2+\cdots +t^{k∕2}=t\frac{t^{k∕2}-1}{t-1}\sim t^{k∕2}$(4) ) we really have that the number of distances $k$ is asymptotically $\frac{e^2}{2}\sim \left(\genfrac{}{}{0ex}{}{e}{2}\right)$ if $k$ is fixed and $t$ is large. This proves the statement for even $k$.

Suppose now that $k>3$ is odd. Define a graph $G(t,k)$ in the following way. It will consist of a complete graph $K_t$ and $t$ copies of the rooted tree $T(t,(k-1)∕2)$, one copy attached to every vertex of $K_t$. The set of leaves of the copy attached to the $i$th vertex is denoted by $L_i$. The number of edges of $G(t,k)$ is (5) $\left(\genfrac{}{}{0ex}{}{t}{2}\right)+t(t+\cdots +t^{(k-1)∕2})\sim t^{(k+1)∕2}.$(5) The distance of the vertices $a\in L_i$ and $b\in L_j(i\ne j)$ in $G(t,k)$ is exactly $k$. Of course $\left|L_i\right|=t^{(k-1)∕2}$. Hence the number of pairs of vertices with distance $k$ is at least (in fact exactly) $\left(\genfrac{}{}{0ex}{}{t}{2}\right){\left(t^{(k-1)∕2}\right)}^2\sim \frac{t^{k+1}}{2}.$Using (5(5) $\left(\genfrac{}{}{0ex}{}{t}{2}\right)+t(t+\cdots +t^{(k-1)∕2})\sim t^{(k+1)∕2}.$(5) ) we obtain that the number of distances is $\frac{e^2}{2}\sim \left(\genfrac{}{}{0ex}{}{e}{2}\right)$, as stated.

In the case of $k=3$ the construction above should be slightly modified. Here we attach a star with $t^2$ edges to each vertex of the complete graph $K_t$. The endpoints of different stars have distance 3. The number of edges is (6) $e=\left(\genfrac{}{}{0ex}{}{t}{2}\right)+t\cdot t^2\sim t^3.$(6) The number of pairs with distance 3 is $\left(\genfrac{}{}{0ex}{}{t}{2}\right)t^2\cdot t^2\sim \frac{t^6}{2}\sim \frac{e^2}{2},$where (6(6) $e=\left(\genfrac{}{}{0ex}{}{t}{2}\right)+t\cdot t^2\sim t^3.$(6) ) was used.

Our constructions show the statement for an infinite sequence of values of $e$, namely for the values of form (⁽⁴⁾(4) $e=t+t^2+\cdots +t^{k∕2}=t\frac{t^{k∕2}-1}{t-1}\sim t^{k∕2}$(4) ⁽⁶⁾(6) $e=\left(\genfrac{}{}{0ex}{}{t}{2}\right)+t\cdot t^2\sim t^3.$(6) ) in the respective cases. This would be sufficient if we knew that $S(e,k)$ is a monotone function of $e$. However it is absolutely non-trivial that adding an edge to a graph increases the distances $k$. Here, however only the monotonicity of our construction is needed.

Suppose that $k$ is even and $t+t^2+\cdots +t^{k∕2}<e<(t+1)+{(t+1)}^2+\cdots +{(t+1)}^{k∕2}.$Add $e-(t+t^2+\cdots +t^{k∕2})$edges to $T(t,k∕2)$ without forming a cycle. No distance $k$ can be destroyed in this way in $T(t,k∕2)$. Therefore the number of distances $k$ in this new graph is at least as much as in $T(t,k∕2)$. This proves that the number of distances $k$ can asymptotically be $\frac{t^k}{2}$ when $e$ is asymptotically at most ${(t+1)}^{k∕2}\sim t^{k∕2}$.

The other cases of $k$ can be similarly settled.  □

If $k$ is very close to $e$ then there is a hope to get the exact value of $S(e,k)$.

Conjecture 1

If $\ell \ge 0$ is fixed, $e$ is large enough then $S(e,e-\ell )=\lfloor \frac{\ell }{2}\rfloor \lceil \frac{\ell }{2}\rceil$.

The construction giving this value is two stars with $\lfloor \frac{\ell }{2}\rfloor$ and $\lceil \frac{\ell }{2}\rceil$ edges connected with a path of $e-\ell$ edges. One easily prove the conjecture for $\ell =0,1,2,3.$

2.3 The case $\ell >1$, paths

Here we consider the inverse problem, again. Let $U(p,\ell ,k)(\ell <k)$ be the largest number of paths of length $k$ in a graph containing $p$ paths of length $\ell$. The most important case is $\ell =k-1$. Having a good upper estimate on $U(p,k-1,k)$ (and $U(p,k-2,k-1)$) we get one for $U(p,k-2,k)$, and so on. Make our notation shorter: $U(p,k)=U(p,k-1,k)$.

Proposition 4

$U(p,k)$ is asymptotically lower bounded by $2^{\frac{1}{k}}{p}^{\frac{k+1}{k}}$.

Proof

The complete graph $K_n$ serves as a construction. The number of paths of length $k-1$ is $p=\frac{n(n-1)\dots (n-k+1)}{2}$ (choosing an ordered sequence of vertices of length $k$, we have to divide the product by 2 because every path is counted starting from both ends). Hence $p\sim \frac{n^k}{2}$ that is $n\sim {\left(2p\right)}^{\frac{1}{k}}$. The number of paths of length $k$ is $\frac{n(n-1)\dots (n-k)}{2}\sim \frac{n^{k+1}}{2}\sim \frac{{\left(2p\right)}^{\frac{k+1}{k}}}{2}=2^{\frac{1}{k}}{p}^{\frac{k+1}{k}}.$  □

Observe that this upper bound is too weak if $k=2$. It gives $\sqrt{2}{p}^{\frac{3}{2}}$ while we know by Proposition 1 that $U(p,2)=R(e,2)=\left(\genfrac{}{}{0ex}{}{e}{2}\right)=\left(\genfrac{}{}{0ex}{}{p}{2}\right).$ However we believe that the bound is asymptotically sharp starting from $k=3$.

Conjecture 2

$U(p,3)\sim 2^{\frac{1}{3}}{p}^{\frac{4}{3}}.$

Theorem 8

Conjecture 1 is true for regular graphs.

Proof

Let $n$ denote the number of vertices of the regular graph of degree $d$. The number of paths of length 2 with middle vertex at a given vertex is $\left(\genfrac{}{}{0ex}{}{d}{2}\right)$. The total number of paths of length 2 is (7) $p=n\left(\genfrac{}{}{0ex}{}{d}{2}\right).$(7) The number of paths of length 3 with a fixed edge in the middle is ${(d-1)}^2$, since we have $(d-1)$ ways to continue the path at each end of the fixed edge. The total number of paths of length 3 is obtained by multiplying this with the number of edges. The number of edges is $\frac{nd}{2}$. Hence the number of paths of length 3 is (8) $\frac{nd}{2}{(d-1)}^2.$(8) We know by Proposition 4 that $2^{\frac{1}{3}}{p}^{\frac{4}{3}}$ is an asymptotic lower bound. Here we will prove that it is also an upper bound for (8(8) $\frac{nd}{2}{(d-1)}^2.$(8) ) that is for the number of paths of length 3: (9) $\frac{nd}{2}{(d-1)}^2\le 2^{\frac{1}{3}}{p}^{\frac{4}{3}}.$(9) Use (7(7) $p=n\left(\genfrac{}{}{0ex}{}{d}{2}\right).$(7) ) on the right hand side. $\frac{nd}{2}{(d-1)}^2\le 2^{\frac{1}{3}}{p}^{\frac{4}{3}}=2^{\frac{1}{3}}{\left(n\left(\genfrac{}{}{0ex}{}{d}{2}\right)\right)}^{\frac{4}{3}}.$Writing out the details this becomes $nd{(d-1)}^2\le n^{\frac{4}{3}}{d}^{\frac{4}{3}}{(d-1)}^{\frac{4}{3}}.$Divide both sides by $nd{(d-1)}^{\frac{4}{3}}.$ We have arrived to ${(d-1)}^{\frac{2}{3}}\le n^{\frac{1}{3}}{d}^{\frac{1}{3}}.$This is true, since the degree cannot exceed the number of vertices. (9(9) $\frac{nd}{2}{(d-1)}^2\le 2^{\frac{1}{3}}{p}^{\frac{4}{3}}.$(9) ) and the theorem are proved.  □

2.4 The case $\ell >1$, distances

Let $T(p,\ell ,k)(\ell <k)$ be the largest number of distances of length $k$ in a graph containing $p$ distances of length $\ell$. The most important case is $\ell =k-1$. Having a good upper estimate on $T(p,k-1,k)$ (and $T(p,k-2,k-1)$) we get one for $T(p,k-2,k)$, and so on. Make our notation shorter: $T(p,k)=T(p,k-1,k)$.

Of course $T(p,2)=S(p,2)$ and Proposition 2 gives the exact solution. The number of distances 2 is a quadratic function of the number of distances 1 (edges). We believe that this cannot happen for larger $k$’s. Actually, it is difficult to construct a graph in which the number of distances 3 is much larger than the number of distances 2.

Theorem 9

$\frac{1}{36}(1-o\left(1\right))plogp\le T(p,3)$where $log$ means logarithm of basis 2.

The proof will be divided into lemmas.

Let the vertices of a graph $G^{d\square }$ be the sequences of length $d$ formed from the elements $-3,-2,-1,0,1,2,3$. Two vertices are adjacent if the corresponding sequences are equal in all but one place where the difference of the values is 1 or $-1$. This is actually a $7\times 7\times \cdots \times 7$ “grid” containing $7^d$ vertices. Let $n(d,t)$ denote the number of vertices having distance $t$ from the origin $(0,0,\dots ,0)$. The case $t=1$ is trivial. (10) $n(d,1)=2d.$(10)

Lemma 1

$n(d,2)=2d^2$.

Proof

Let $H$ denote the set of vertices of distance 2 from the origin in $G^{(d+1)\square }$. Divide $H$ into subsets according to their first coordinates: $H(-2),H(-1),H\left(0\right),H\left(1\right),H\left(2\right).$ Then (11) $\left|H\right|=\left|H(-2)\right|+\left|H(-1)\right|+\left|H\left(0\right)\right|+\left|H\left(1\right)\right|+\left|H\left(2\right)\right|.$(11)

The elements of $H\left(0\right)$ have distance 2 in the rest, that is in $G^{d\square }$. Hence we have (12) $\left|H\left(0\right)\right|=n(d,2).$(12) The elements of $H\left(1\right)$ have a value 1 in the first coordinate. Therefore their rest have distance 1 from the origin. Hence we have (13) $\left|H\left(1\right)\right|=n(d,1).$(13) The same holds for $H(-1)$: (14) $\left|H(-1)\right|=n(d,1).$(14) Finally, if the first coordinate is $2$ or $-2$ then the other $d$ coordinates must be all 0. Hence we have (15) $\left|H\left(2\right)\right|=\left|H(-2)\right|=1.$(15) Eqs. (10)–(15) give (16) $n(d+1,2)=n(d,2)+4d+2.$(16) Now use induction on $d$ to prove the statement of the lemma. For $d=1$, it is trivial that there are two vertices of distance 2 from the point 0. Suppose now that the statement holds for $d$ and prove it for $d+1$. By (16(16) $n(d+1,2)=n(d,2)+4d+2.$(16) ) and the inductional hypothesis we can write $n(d+1,2)=2d^2+4d+2=2{(d+1)}^2.\square$

Lemma 2

$n(d,3)=\frac{4}{3}{d}^3+\frac{2}{3}d$.

Proof

The logic of the previous proof will be used again. Let $H$ denote the set of vertices of distance 3 from the origin in $G^{(d+1)\square }$. Divide $H$ into subsets according to their first coordinates: $H(-3),H(-2),H(-1),H\left(0\right),H\left(1\right),H\left(2\right),H\left(3\right).$ Then (17) $\left|H\right|=\left|H(-3)\right|+\left|H(-2)\right|+\left|H(-1)\right|+\left|H\left(0\right)\right|+\left|H\left(1\right)\right|+\left|H\left(2\right)\right|+\left|H\left(3\right)\right|.$(17)

The elements of $H\left(0\right)$ have distance 3 in the rest, that is in $G^{d\square }$. Hence we have (18) $\left|H\left(0\right)\right|=n(d,3).$(18) The elements of $H\left(1\right)$ have a value 1 in the first coordinate. Therefore their rest have distance 2 from the origin. Hence we have (19) $\left|H\left(1\right)\right|=n(d,2).$(19) The same holds for $H(-1)$: (20) $\left|H(-1)\right|=n(d,2).$(20) If the first coordinate of a vertex is 2 then the rest must have distance 1 from the origin. This proves (21) $\left|H\left(2\right)\right|=n(d,1)$(21) and (22) $\left|H(-2)\right|=n(d,1).$(22) Finally, if the first coordinate is $3$ or $-3$ then the other $d$ coordinates must be all 0. Hence we have (23) $\left|H\left(3\right)\right|=\left|H(-3)\right|=1.$(23) Eqs. (17)–(23) give (24) $n(d+1,3)=n(d,3)+2n(d,2)+4d+2$(24) and, using the statement of Lemma 1, (25) $n(d+1,3)=n(d,3)+4d^2+4d+2.$(25) Now use induction on $d$ to prove the statement of the lemma. For $d=1$, it is trivial that there are two vertices of distance 3 from the point 0. Suppose now that the statement holds for $d$ and prove it for $d+1$. By (25(25) $n(d+1,3)=n(d,3)+4d^2+4d+2.$(25) ) and the inductional hypothesis we can write $n(d+1,3)=\frac{4}{3}{d}^3+\frac{2}{3}d+4d^2+4d+2=\frac{4}{3}{(d+1)}^3+\frac{2}{3}(d+1).\square$

Proof of Theorem 9

Modify the graph $G^{d\square }$ at the beginning of our proof. Let the vertices of the graph $Z_8^{d\square }$ be the sequences of length $d$ formed from the elements $-3,-2,-1,0,1,2,3,4$ and consider these integers modulo 8. Two vertices are adjacent if the corresponding sequences are equal in all but one place where the difference of the values is 1 or $-1$ (mod 8). This is actually a $8\times 8\times \cdots \times 8$ “cyclic grid” containing $8^d$ vertices. The 3-neighborhood of a vertex $v$ in a graph is the subgraph spanned by the set of vertices of distance at most 3 from $v$. Observe that the 3-neighborhoods of the origins in $G^{d\square }$ and $Z_8^{d\square }$ are isomorphic. Moreover the 3-neighborhoods of two distinct vertices in $Z_8^{d\square }$ are also isomorphic. Hence it follows that the number of vertices with distance 3 (resp. 2) from a vertex of $Z_8^{d\square }$ is the same as the number of vertices with distance 3 (resp. 2) from the origin of $G^{d\square }$. Summarizing, the number of vertices with distance 3 (resp. 2) from a vertex of $Z_8^{d\square }$ is $n(d,3)$ (resp. $n(d,2)$). Therefore the total number of distances 2 in $Z_8^{d\square }$ $p=\frac{1}{2}{8}^{d}n(d,2).$By Lemma 1 this is equal to (26) $p=\frac{1}{2}{8}^d\cdot 2d^2=8^d\cdot d^2.$(26) Similarly, the total number of distances 3 in $Z_8^{d\square }$ $\frac{1}{2}{8}^{d}n(d,3)$and by Lemma 2 this is equal to (27) $8^d\left(\frac{2}{3}{d}^3+\frac{1}{3}d\right).$(27) Here (26(26) $p=\frac{1}{2}{8}^d\cdot 2d^2=8^d\cdot d^2.$(26) ) and (27(27) $8^d\left(\frac{2}{3}{d}^3+\frac{1}{3}d\right).$(27) ) lead to (28) $8^d\left(\frac{2}{3}{d}^3+\frac{1}{3}d\right)\le T(8^d\cdot d^2,3).$(28) Eq. (26(26) $p=\frac{1}{2}{8}^d\cdot 2d^2=8^d\cdot d^2.$(26) ) gives us $plogp=8^d{d}^2(3d+2logd).$Compare this with the left hand side of (28(28) $8^d\left(\frac{2}{3}{d}^3+\frac{1}{3}d\right)\le T(8^d\cdot d^2,3).$(28) ). One can see that (29) $\frac{2}{9}(1-o\left(1\right))plogp=\frac{2}{9}(1-o\left(1\right))8^d{d}^2(3d+2logd)\le 8^d\left(\frac{2}{3}{d}^3+\frac{1}{3}d\right).$(29) The inequalities (28(28) $8^d\left(\frac{2}{3}{d}^3+\frac{1}{3}d\right)\le T(8^d\cdot d^2,3).$(28) ) and (29(29) $\frac{2}{9}(1-o\left(1\right))plogp=\frac{2}{9}(1-o\left(1\right))8^d{d}^2(3d+2logd)\le 8^d\left(\frac{2}{3}{d}^3+\frac{1}{3}d\right).$(29) ) prove the statement of the theorem in a stronger form, but only for some special values of $p$, which form an exponential sequence.

Let us prove now the weaker inequality for the intermediate values of $p$. Suppose (30) $p_1=8^d{d}^2<p<8^{d+1}{(d+1)}^2=p_2.$(30) Add $p-8^d{d}^2$ paths of length 2 to $Z_8^{d\square }$ in such a way that they do not form any cycle neither with $Z_8^{d\square }$ nor with each other. The so obtained graph $G$ contains $p$ pairs with distance 2 and at least (27(27) $8^d\left(\frac{2}{3}{d}^3+\frac{1}{3}d\right).$(27) ) pairs with distance 3.

Observe that (31) $\frac{1}{8}(1-o\left(1\right))p_{2}log{p}_2=p_{1}log{p}_1.$(31) Formulas (30(30) $p_1=8^d{d}^2<p<8^{d+1}{(d+1)}^2=p_2.$(30) ) and (31(31) $\frac{1}{8}(1-o\left(1\right))p_{2}log{p}_2=p_{1}log{p}_1.$(31) ) imply $\frac{1}{36}(1-o\left(1\right))plogp\le \frac{2}{9}(1-o\left(1\right))p_{1}log{p}_1.$Combining this with (29(29) $\frac{2}{9}(1-o\left(1\right))plogp=\frac{2}{9}(1-o\left(1\right))8^d{d}^2(3d+2logd)\le 8^d\left(\frac{2}{3}{d}^3+\frac{1}{3}d\right).$(29) ) the desired inequality is obtained.  □

Open Problem 1

Find a non-trivial upper bound on $T(p,3)$.

Notes

Peer review under responsibility of Kalasalingam University.