Five results on maximizing topological indices in graphs

Assume this proposition is not true. In that case there exist some $n$ and $m$ such that $\mathbb{T}(n,m)$ and $\mathbb{T}(n,m+1)$ are both nonempty and $\operatorname{W}_{f}(\mathbb{T}(n,m))\geq\operatorname{W}_{f}(\mathbb{T}(n,m+1)).$ For some fixed $n$, we take the least integer $m$ for which $\operatorname{W}_{f}(\mathbb{T}(n,m))\geq\operatorname{W}_{f}(\mathbb{T}(n,m+1))$ holds and take an extremal graph $G\in\mathbb{T}(n,m)$ with $\operatorname{W}_{f}(G)=\operatorname{W}_{f}(\mathbb{T}(n,m))$.

Since $G$ is a tree which is not a path (as a path reaches the largest possible matching number), we can choose a leaf $\ell$ and a vertex $w$ of degree at least $3$ such that $d(w,\ell)$ is the smallest among all such choices. Considering $G$ as a rooted tree in $w$, there are at least three branches, the path $P$ from $\ell$ to $w$ being one of them. Let $S$ be a branch different from $P$ and $S^{\prime}$ be the union of the remaining branches different from $P$ and $S$. Here we do not consider $w$ as a vertex of $S$ nor of $S^{\prime}$. We can prune the subtree $S$ (with root $w$) and regraft it at $\ell$. After this operation, the set of distances between $P$ and $S$ or $S^{\prime}$ is the same as before, while the distance between any vertex of $S^{\prime}$ and any vertex of $S$ has increased with $d(w,\ell)$. Since $f$ is a strictly increasing function, this implies that $\operatorname{W}_{f}$ has strictly increased by performing the SPR operation, while the matching number has not increased with more than one. This implies that $\operatorname{W}_{f}(G)=\operatorname{W}_{f}(\mathbb{T}(n,m))\geq\operatorname{W}_{f}(\mathbb{T}(n,i))$ for every $i\leq m+1$ was not true. This contradiction implies that the proposition is true.

If the proposition is not true, there is an extremal graph $G$ with a subtree $S$ connected to some $u_{i}$ with $1<i<d-1.$ Let $G_{1}$ and $G_{2}$ be the graphs by pruning and regrafting $S$ at $u_{1}$ resp. $u_{d-1}$. Let $H$ be the graph $G\backslash S,$ i.e. the graph $G$ when $S$ is pruned Note that every neighbour of a leaf will be in a maximum matching. In particular, without loss of generality, we can assume $u_{0}u_{1}$ and $u_{d-1}u_{d}$ are edges in a maximum matching of $H,G,G_{1}$ or $G_{2}$. This implies that the matching number of both $G_{1}$ and $G_{2}$ is exactly equal to $m(H)+m(S),$ while the matching number of $G$, $m(G)$, is at least equal to $m(H)+m(S)$ (and plausible one larger). So the matching number of both $G_{1}$ and $G_{2}$ is not larger than the matching number of $G.$ Let $S_{1}$ be the copy of $S$ which is connected to $u_{1}$ and $S_{2}$ be the copy of $S$ which is connected to $u_{d-1}.$ We will prove that

For every $v\in H,v^{\prime}\in S$ (here we take $v^{\prime}$ in $S_{1}$ as the vertex corresponding to the original $v^{\prime}$ and similarly in $S_{2}$) we have $(d-1-i)d_{G_{1}}(v^{\prime},v)+(i-1)d_{G_{2}}(v^{\prime},v)\geq(d-2)d_{G}(v^{\prime},v)$ since $(d-1-i)d_{G}(u_{1},v)+(i-1)d_{G}(u_{d-1},v)\geq(d-2)d_{G}(u_{i},v).$ Since $f$ is convex and strictly increasing, $(d-1-i)f\left(d_{G_{1}}(v^{\prime},v)\right)+(i-1)f\left(d_{G_{2}}(v^{\prime},v)\right)\geq(d-2)f\left(d_{G}(v^{\prime},v)\right).$ From this and the fact that it is strict for $v=u_{i}$, Equation (1) follows. Hence at least one of the two graphs $G_{1}$ or $G_{2}$ has a larger generalized Wiener index than $G$ and so taking into account Proposition 2.3 we conclude $G$ was not extremal.

As a consequence of Proposition 1, the extremal graph is a path $u_{1}u_{2}u_{3}\ldots u_{d-1}$ with $a$ pendent vertices to $u_{1}$ and $b$ pendent vertices to $u_{d-1}$, where $a,b\geq 1$. The maximum of the generalized Wiener index $\operatorname{W}_{f}$ for such a graph with matching number equals $m$ clearly needs a diameter being equal to $2m$ if $n\geq 2m+1$ and is the path if $n=2m.$ Since

with $f$ strictly increasing, i.e. $f(d)-f(2)>0$, the maximum occurs when $\lvert a-b\rvert\leq 1$ as we are considering the nontrivial case with $d\geq 3$ (as $m\geq 2$) and $a+b=n-(2m-1)$ being fixed.

Note that for any graph, the sum $\alpha+m\leq n$, since given an independent set $I$ and a matching $M$, any edge of $M$ contains at least one vertex which is not in $I.$ This implies that $m\leq n-\alpha\leq\frac{n}{2}.$ Applying Proposition 2.3 (recall extremal graphs with respect to $m$ are trees) and Theorem 2.4, we have that $\operatorname{W}_{f}(G)\leq\operatorname{W}_{f}(\operatorname{A}_{n,n-\alpha})$. Since the graph $\operatorname{A}_{n,n-\alpha}$ has independence number $\alpha$, it is the unique extremal graph.

The function $f\colon x\mapsto x^{j}$ is a convex function on $\mathbb{R}^{+}$ when $j\geq 1$. Note that for this $f$, we have $\mu_{j}(G)=\sqrt[j]{\frac{\operatorname{W}_{f}{G}}{\binom{n}{2}}}.$ So from the previous two theorems, we know the maximum is attained when $G$ equals $\operatorname{A}_{n,n-\alpha}$ or $\operatorname{D}_{n,\alpha}.$ Note that for every $1\leq i\leq\alpha-1$, there are more pairs of vertices $\{u,v\}$ with $d(u,v)=i$ then pairs with $d(u,v)=2\alpha-i$ in the extremal graph. Combining with $\operatorname{M}_{j}(1,2\alpha-1)\geq\operatorname{M}_{j}(i,2\alpha-i)$ (true by the inequality of Jensen), we conclude.

Let $U=\{u\in V(G),\deg(u)>1\}$ be the sets of nonleafs, which has size $n-\ell.$ Note that for every leaf $v$, $G[U\cup\{v\}]$ is a connected graph and hence

Equality holds if and only if $G[U]$ is a path and $v$ is connected to an endvertex of $G[U]$. The second part is Theorem 4 of Gutman et al. (2009), with the addition that it is also true for $\ell\in\{2,3\}.$

Assume $T$ is the extremal graph and it has $\ell$ leaves. Note that

is bounded by

due to Lemma 3. Equality in the first part holds if and only if $T$ is a double broom. A double broom for which equality holds in the second equality need to be balanced and balanced double brooms attain equality. The maximum among all graphs is now attained by the double brooms having $\ell$ leaves, where $2\leq\ell\leq n-1$ is an integer maximizing the expression.

We can prove this by induction, the $n=2k$ case being the trivial base case as $C_{2k}$ is the only unicyclic graph on $2k$ vertices containing a $C_{2k}.$ Assume the lemma is true for $n-1\geq 2k$. Any unicyclic graph $G$ of order $n>2k$ containing a $C_{2k}$ has at least one leaf $v$. Let $H=G\backslash v$. Note that the distance from $v$ to the $C_{2k}$ is at most $n-2k$ and the diameter of $G$ is at most $n-k$. At least $k-1$ consecutive distances between $v$ and vertices of $C_{2k}$ appear twice, these are at most $n-2k+1$ up to $n-k-1$. Thus $\sum_{u\in H}d(v,u)\leq\sum_{i=1}^{n-k}i+\sum_{i=n-2k+1}^{n-k-1}i$ and together with the induction hypothesis on $H$, we get the result.

Note that a graph $G$ having bipartition of sizes $q\geq p$ has a matching number $m$ which is at most $p$. If $q\geq p+3$, the result is a consequence of Theorem 7.1 and Proposition 2.1 from Cambie (2019) applied on $n=p+q$ and $m=p$. If $q\in\{p,p+1\}$, we have to take the maximum over all possible graphs containing an even cycle.

The maximum for the graphs in Lemma 4 is attained when $k=2$. There are multiple ways to see this. Let $G$ be $C_{2k}$ with a path $P_{n-2k}$ attached to it. Let $v$ be a neighbour of the vertex with degree $3$, or a random vertex of $G=C_{2k}$ if $n=2k.$ Then

Equality holds if and only if $k=2.$

If $q=p+2$, we know the extremal graph containing a $C_{4}$ with $n=2p+2$ and $m\leq p$ is $G^{4}_{n/2-m,n/2-m,2m-4}$ by Section $7$ in Cambie (2019). Furthermore $W(G^{4}_{n/2-m,n/2-m,2m-4})<W(G^{4}_{1,1,2p-4})$ if $m<p$.

The graph $G^{4}_{1,1,2p-4}$ has a larger Wiener index than the extremal graphs in Lemma 4 for $k\geq 3$, from which we conclude again. For this it is enough to note that for all $k\geq 3$, we have

as adding the path of order $n-2k$ to both structures only makes the difference larger.

Let $e=uv$ and assume $(W-\varepsilon)(G)>(W-\varepsilon)(G\backslash e).$ Suppose the shortest cycle in $G$ containing $e$ is $C_{k}$. Note that distances do not decrease when deleting edges, so we have to focus on the eccentricities that increase. Let $z$ be a vertex not belonging to $C_{k}$ for which the eccentricity increases when deleting $e$. Without loss of generality we can assume $d(z,u)<d(z,v)$. Let $\operatorname{ecc}_{G\backslash e}(z)=d_{G\backslash e}(z,t)$ for a vertex $t$ (where possible $t=v$). Then we know that $d(z,t)<d_{G\backslash e}(z,t)$, so the shortest path from $z$ to $t$ in $G$ uses the edge $uv$ and so $d(z,t)=d(z,v)+d(v,t).$ This also implies that $d(v,t)=d_{G\backslash e}(v,e).$ Combining these observations with the definition of eccentricity and the triangle inequality, we get that

As the difference in eccentricity for $z$ is cancelled by the difference of distance between $z$ and $v$, while $z$ was taken arbitrary, $(W-\varepsilon)(G)>(W-\varepsilon)(G\backslash e)$ implies that

which is only the case if $k\in\{3,5\}$ and then the difference is exactly equal to $1$.

Case: $k=3$ To have a contradiction, both $\operatorname{ecc}(u)$ and $\operatorname{ecc}(v)$ need to increase when deleting $e$. This implies there is a vertex $w$ such that $3\leq\operatorname{ecc}(u)=d(w,u)<d_{G\backslash e}(w)$. Let $v_{2}$ be the neighbour of $v$ on a shortest path in $G$ from $v$ to $w.$ Then $d_{G\backslash e}(v_{2},u)=d(v_{2},u)+1.$ So if $\operatorname{ecc}_{G\backslash e}(v_{2})=\operatorname{ecc}(v_{2})$, we have an additional difference that (in the expansion of $W(G\backslash e)-W(G)$) is at least $1$, leading to a contradiction. If $\operatorname{ecc}_{G\backslash e}(v_{2})>\operatorname{ecc}(v_{2})\geq 3$, there is an other vertex $x$ not belonging to the $C_{3}$ such that $d_{G\backslash e}(x,v_{2})>d(x,v_{2})$ and we conclude again.

Case: $k=5$ In this case, let $v_{2}$ be the neighbour from $v$ in the $C_{5}$ different from $u$. When doing the check in the reduced case that $(W-\varepsilon)(C_{k})>(W-\varepsilon)(P_{k})$, we take into account that the eccentricity of $v_{2}$ goes up by $1$ in $C_{5}$. So $(W-\varepsilon)(G)>(W-\varepsilon)(G\backslash e)$ is only possible if $\operatorname{ecc}_{G\backslash e}(v_{2})>\operatorname{ecc}(v_{2}).$ But since $\operatorname{ecc}(v_{2})\geq 3$, there is a vertex $x$ not belonging to the $C_{5}$ for which $d_{G\backslash e}(v_{2},x)>d(v_{2},x).$ As we did not take this difference into account before when looking to $(W-\varepsilon)(G)-(W-\varepsilon)(G\backslash e)$, we conclude that $(W-\varepsilon)(G)\leq(W-\varepsilon)(G\backslash e)$ again.

First, one can check that $W(G)-\varepsilon(G)$ is smaller than $(W-\varepsilon)(P_{n})$ when $15\geq n\geq 9$ in case $G$ has radius at most $2$. For $n=9$, a brute force check confirms. For $n=10$, if the diameter is at most $3$, then $W(G)\leq 97$ and $\varepsilon(G)\geq 10$ and we are done. If the diameter is $4$, we have $W(G)\leq 117$ and $\varepsilon(G)\geq 2\cdot 4+2\cdot 3+6\cdot 2=26$, so $W(G)-\varepsilon(G)\leq 91<95=(W-\varepsilon)(P_{10}).$ The cases $11\leq n\leq 15$ work similarly. For $n\geq 16$, note that the diameter of $G$ is bounded by $4$ and so $W(G)\leq 4\binom{n}{2}<(W-\varepsilon)(P_{n}).$

So from now on, we only have to consider graphs with radius at least $3$ and hence by Lemma 5 we can first focus on trees. A bruteforce check by computer over all trees of order $9\leq n\leq 20$ verifies the theorem for these values. For $n\geq 21$, we first observe that the diameter of an extremal graph is at least $7$, since otherwise $(W-\varepsilon)(G)\leq 6\binom{n}{2}-3n<(W-\varepsilon)(P_{n}).$ Now we can prove the statement by induction. If the diameter $d$ equals $n-1$, we have the path $P_{n}$. If the diameter is smaller, $d\leq n-2$, one can remove a leaf $v$ which is not part of the diameter. Now the eccentricities of all vertices different from $v$ are the same in $G$ and $G\backslash v$. By the induction hypothesis, we have $(W-\varepsilon)(G\backslash v)\leq(W-\varepsilon)(P_{n-1}).$ Furthermore we have

from which we conclude. This implies that $P_{n}$ is the unique tree maximizing $(W-\varepsilon)(G).$ By Lemma 5 no graph with a spanning tree which is not a path can be extremal (note that the radius does not decrease when removing edges). Since the cycle $C_{n}$ (and the path $P_{n}$ itself) is the only graph which has only $P_{n}$ a spanning graph, but $(W-\varepsilon)(C_{n})<(W-\varepsilon)(P_{n})$ for $n>5$, as concluded from the computation in Equation 2, the path $P_{n}$ is the unique extremal graph.

Let $U$ be the set of vertices different from the ones on the diameter $v_{0}v_{1}\ldots v_{d}$. Then $\sum_{u,v\in U}d(u,v)\leq 2\binom{n-d-1}{2}$ with equality if and only if they are all connected to the same vertex on the diameter. We note that for every $u\in U$, $\sum_{0\leq i\leq d}d(u,v_{i})-\varepsilon(v)$ is minimal if $u$ is connected to a central vertex and equality is also possible if it is connected to a neighbouring vertex of a central vertex when $d+1$ is odd as then there is only one central vertex. Here we use that $d(v_{j},v_{i})+d(v_{j},v_{d-i})\geq d-2i$ where $u_{j}$ is the neighbour of $u$ and $0\leq i<\frac{d}{2}$.