On investigations of graphs preserving the Wiener index upon vertex removal

1.   Introduction

The topological indices (TIs) are found to be one of the effective tools in determining the properties such as: boiling point, melting point and bond energy of each compound. These are certain parameters that represent the physical and biochemical properties of different compounds depending upon their structures. TIs are helpful in describing the qualitative as well as quantitative analysis of a given molecular structure. Several aspects of TIs are still being vastly studied by different researchers, some recent contributions include ^[13,16]. Use of TIs in drugs and chemistry are mentioned in ^{[3,19,20,21,22]} and few other applications can be seen in ^[9,10,12,15].

Before proceeding further, we set the notations of this paper. We denote an undirected connected graph with no multiple edge or loop by $G$, the number of edges and vertices by $m$ and $n$, respectively, a cycle with $n$ vertices by $C_n$, complete graph by $K_n$, degree of a vertex $v$ in $G$ by $d_G(v)$ (or simply $d(v)$) and the distance between the vertices $u$ and $v$ by $d(u, v)$. The Wiener index of $G$ is defined as

The main objective of producing this index was to determine the boiling points of alkanes ^[17]. Wiener index is also implicitly used in network topology as it plays a vital role in the computation of average distance which is an important measure in the network topology. It is also known due to its frequent use in communication theory and facility location, sociometry and crystallography, for details see ^[2], ^[4] and references therein. Due to its vast applications, the Wiener index and its different variants have been studied extensively, for example see ^[1,6,7,18] and surveys ^[8,11].

Although, the study of several papers comprises of different aspects of Wiener index, but there are still unsolved problems related to this descriptor. The attempts to solve these problems have resulted in to formulations and solutions of new variants of related problems as well. In ^[14], Šoltés posed the question of finding all graphs $G$ for which $W(G)$ does not change upon removal of any vertex. Up to now, the only such known graph is $C_{11}$. Recently, Knor et al. ^[4] studied some relaxed versions of this problem and produced partial solutions to those problems. In this paper, we solved an open problem which was formulated by Knor et al. during their investigations on relaxed version of Šoltés problem.

Before presenting the main results, we recall the formulations of the related problems: we start with the Šoltés ^[14] problem:

$\bf{Problem}$ $1$: Find all possible graphs $G$ such that $W(G) = W(G-\{v\})$, for any vertex $v$ in $G$. The first graph, which is $C_{11}$, with this property was found by Šoltés himself. Till now, several efforts have been made to solve this problem. However, Problem 1 still remains open until now. Knor et al. ^[5] investigated a relaxed version of the Problem 1 by considering:

$\bf{Problem}$ $2$: Find all possible graphs $G$ such that $W(G) = W(G-\{v\})$ is true for some $v\in V(G)$. They constructed many infinite classes of graphs $G$ in which $W(G) = W(G-\{v\})$ for some vertex $v$ of degree $2$. Recently, in ^[4], some infinite classes of graphs $G$ with a vertex $v$ such that $d(v) \geq 3$ and $W(G) = W(G-\{v\})$ are constructed. Other than that, the existence of vertices of degree $n-2$ and $n-1$ in an $n$-vertex graph $G$ with $W(G) = W(G-\{v\})$ have also been shown in ^[4]. But, finding all such graphs is still a quite challenging problem. Knor et al. ^[4] continued to study this problem and formulated the following three problems as well:

$\bf{Problem}$ $3$: Are there $k$-regular connected graphs $G\neq C_{11}$ with $W(G) = W(G-\{v\})$ for some $v \in V(G)$?

$\bf{Problem}$ $4$: Find connected graphs $G$ with $W(G) = W(G-S)$ where $S \subseteq V(G)$ is arbitrary and $| S | \geq 2$.

$\bf{Problem}$ $5$: For a given $r$, find (infinitely many) graphs $G$ with $W(G) = W(G-\{v_1\}) = W(G-\{v_2\}) = \cdots = W(G-\{v_r\})$ for some distinct vertices $v_1, \cdots, v_r \in V (G)$.

An infinite family of graphs $G$ with $W(G) = W(G-\{v_i\})$ for some vertices $v_i$ of $G, i = 1, ..., k$ ($k$ is an arbitrary natural number) is constructed in ^[23]. Moreover, the symmetry of $G$ leads to the following property: $W(G) = W(G-\{v_1 \}) = ... = W(G-\{v_k \})$.

In this paper, we extend the study of the work presented in ^[4] by solving Problem 5. The following section contains the main results of this paper.

2.   Results

We start the section by introducing the following symbols and notations. For an integer $r \geq 1$, a star with $r+1$ vertices is called an $(r+1)$-star and the vertex with the maximum degree is called the center. For $r_1\geq 1$, $r_2\geq 2$, $H(r_1, r_2)$ is a graph obtained from the $(r_1+1)$-star and $K_{r_2}$ by adding an edge $uv$ where $u$ is the center of an $(r_1+1)$-star and $v$ is a vertex of $K_{r_2}$, so $H(r_1, r_2)$ has $r_1 + r_2 + 1$ vertices. We declare that $t_{G}(u) = \sum\limits_{v\in V(G)-\{u\}}d(u, v)$.

For a given graph $G$, the integers $r \geq 2$ and $|V(G)|+r-1\leq q\leq \frac{r(r+2|V(G)|-1)}{2}$, we define a set of graphs $\mathcal{T}(G, r, q)$ as follows:

i.e. $\mathcal{T}(G, r, q)$ is a set of the graphs $G'$ obtained from $G$ by adding $r$ vertices $\{u_1, \ldots, u_r\}$ and $q$ edges such that $d_{G'}(u_1) = |V(G)| + r - 1$, $V(G') = \{u_1, \ldots, u_r\} \cup V(G), G'[V(G)] = G$. Clearly, if $|V(G)|+r-1\leq q\leq \frac{r(r+2|V(G)|-1)}{2}$, we have $\mathcal{T}(G, r, q)\neq \emptyset$.

Given two trees $T_1$, $T_2$ with $v_i \in V(T_i)$ for $i = 1, 2$ and an integer $k \geq 1$, let $T_1^j \cong T_1$ and $T_2^j \cong T_2$ with $f(v_1^j) = v_1$ and $f(v_2^j) = v_2$ under an isomorphic mapping $f$ for $j = 1, 2, \cdots, k$. Now we define a graph, denoted by $G' = G(T_1, T_2, k, v_1, v_2)$ (see Figure 1), with

Lemma 1. For a graph $G$, if there is a vertex $v\in V(G)$ with $d(v) = n - 1$, then we have $W(G) = n(n-1) - m$.

Proof. Since there is a vertex $v\in V(G)$ with $d(v) = n - 1$, then for any vertex $u \in V(G)$, we have $d(u, v)\leq 2$.

Since there are $m$ pairs of vertices $u, v$ with $d(u, v) = 1$, there are $\frac{n(n-1)}{2}-m$ pairs of vertices $u, v$ with $d(u, v) = 2$. Therefore, we have $W(G) = m + 2(\frac{n(n-1)}{2}-m) = n(n-1) - m$.

Lemma 2. For integers $r_1 \geq 1$ and $r_2 \geq 2$, let $H = H(r_1, r_2)$. Then we have $W(H) = n^2 - \frac{3}{2}r_2^2 + nr_2 - 3n + \frac{3}{2}r_2 + 1$ and $m = n - r_2 + \frac{r_2(r_2-1)}{2}$.

Proof. By the definition of $H(r_1, r_2)$, we assume that $G_1$ is the $(r_1+1)$-star, $G_2$ is a $K_{r_2}$, and $uv\in E(H)$ with $u\in V(G_1), v\in V(G_2)$. Then $V(H(r_1, r_2)) = V(G_1)\cup V(G_2)$. For any vertex $w_1\in V(G_1)-\{u\}$, we have $t_H(w_1) = 2r_1 + 1 + 3(r_2 - 1)$. For any vertex $w_2\in V(G_2)-\{v\}$, we have $t_H(w_2) = (r_2 - 1) + 2 + 3r_1$. Since $t_H(u) = r_1 + 1 + 2(r_2 - 1), t_H(v) = r_2 + 2r_1$, therefore

Also, we have

By using Eq (2.2) in Eq (2.1), we get

By counting the edges of $H$, we have $m = r_1 + 1 + \frac{r_2(r_2-1)}{2} = n - r_2 + \frac{r_2(r_2-1)}{2}$.

Lemma 3. For any integer $r\geq 2$, let $y, r_2, q$ be three integers with $r_2 = 2r, y\geq r+\frac{4r^2 - 1}{r - 1}, q = -1-r+r^2+r_2^2+y+2yr-yr_2$. Let $H = H({y-1-r_2, r_2})$. Then, for any graph $G\in \mathcal{T}(H, r, q)$, we have $W(G) = W(H)$.

Proof. We first show that $r+y-1\leq q\leq \frac{r(r+2y-1)}{2}$. Since $q = -1 - r + r^2 + r_2^2 + y + 2yr - yr_2$, we have $q - (r+y-1) = -2r + r^2 + r_2^2 + 2yr - yr_2$. Moreover, $r\geq 2, r_2 = 2r\geq 4$ yield $r^2 - 2r\geq 0, r_2^2 > 0, 2yr - yr_2 = 0$, thus we have $q - (r+y-1)\geq 0$. Now, we will show that $q\leq \frac{r(r+2y-1)}{2}$:

Since $y\geq \frac{4r^2 - 1}{r - 1}, 1-r < 0$, we have $y(1-r)\leq (1-r)\frac{4r^2 - 1}{r - 1}\leq -4r^2 + 1$. Then, we have

Consequently, we have $r+y-1\leq q\leq \frac{r(r+2y-1)}{2}$. Then $\mathcal{T}(H, r, q)\neq \emptyset$. By Lemma 2, $W(H) = y^2 - \frac{3}{2}r_2^2 + yr_2 - 3y + \frac{3}{2}r_2 + 1$. Furthermore, for a graph $G\in \mathcal{T}(H, r, q)$, $|V(G)| = n = y + r$, $|E(G)| = m = |E(H)| + q$. By Lemma 1, we have $W(G) = n(n-1)-m = (y+r)(y+r-1) - |E(H)| - q$, and by Lemma 2, we have $|E(H)| = (y - r_2 + \frac{r_2(r_2-1)}{2})$, then we have $W(G) = y^2 + 2yr + r^2 - y - r - (y - r_2 + \frac{r_2(r_2-1)}{2}) - (-1-r+r^2+r_2^2+y+2yr-yr_2) = y^2 + r_2y - 3y - \frac{3r_2^2}{2} + \frac{3r_2}{2} + 1 = W(H)$. Thus for any graph $G\in \mathcal{T}(H, r, q)$ $W(G) = W(H)$ which completes the proof.

Lemma 4. For a graph $G$ and $r\geq 1$, let there be $r$ vertices $u_1, \ldots, u_r$ such that $W(G) = W(G-\{u_1, \ldots, u_r\})$. Denote by $G' = G-\{u_1, \ldots, u_r\}$, then there is a vertex $v\in V(G')$ with $t_{G'}(v) - t_G(v)\geq r$.

Proof. Suppose to the contrary, we have $t_{G'}(v) - t_G(v) < r$ for any $v\in V(G')$. Clearly, we have $t_G(v)\geq n - 1$ for any $v\in V(G)$. Since $W(G) = \frac{1}{2}\sum\limits_{i = 1}^nt_G(u_i), W(G') = \frac{1}{2}\sum\limits_{i = 1}^{n-r}t_{G'}(u_{i+r}), W(G) = W(G')$. Then, we have $2(W(G) - W(G')) = \sum\limits_{i = 1}^r(t_G(u_i)) + \sum\limits_{i = r+1}^n(t_G(u_i) - t_{G'}(u_i)) > r(n-1) - r(n - r) = r^2 - r\geq 0$, a contradiction with $W(G) = W(G')$.

Lemma 5. For three integers $r, m, k$ with $m\geq r\geq 2, \frac{(1+rk)rk}{2}\geq m$, there is a set of trees $\mathcal{F}\neq \emptyset$ such that $|V(T)| = rk+1$ and there is a vertex $v\in V(T)$ with $t_T(v) = mk$ for any $T\in \mathcal{F}$.

Proof. First we consider following equations:

Let $V_i(T, v_0) = \{v|d_T(v, v_0) = i\}$. Clearly, for $x_1, x_2, \ldots, x_j$, if all $x_i's$ are in $N^+$, then there is a tree $T$ and $v_0\in V(T)$ with $|V_i(T, v_0)| = x_i, |V(T)| = z_1 + 1$. And for this tree $T$, we have $|V(T)| = z_1 + 1, t_T(v_0) = z_1 +\ldots + z_j$. Clearly, if $z_{i+1} < z_{i}$ for any $1\leq i\leq j-1$, there is a solution $x_1, x_2, \ldots, x_j$ in which all $x_i$'s are in $N^+$.

So if we can find $z_1, \ldots, z_j$ with $z_1 = rk, z_1 +\ldots + z_j = mk$, and $z_{i+1} < z_{i}$ for any $1\leq i\leq j-1$, then we can get the tree as required. If $m\geq r\geq 2, \frac{(1+rk)rk}{2}\geq m$, we do following procedure:

(1) Let $z_1 = rk, i = 1$.

(2) If $mk-\sum\limits_{k = 1}^{i}z_k > z_i-1$, let $z_{i+1} = z_i - 1, i = i + 1$ and go to step 2, else let $z_{i+1} = mk-\sum\limits_{k = 1}^{i}z_k$.

Since $rk+(rk-1)+\ldots+1 = \frac{(1+rk)rk}{2}\geq m$, we can get $z_1, \ldots, z_j$ with $z_1 = rk, z_1 +\ldots + z_j = mk$, and $z_{i+1} < z_{i}$ for any $1\leq i\leq j-1$.

Theorem 1. For any $r\geq 2$, there are infinitely many graphs $G$ for which $W(G) = W(G-\{v_1, \ldots, v_r\})$ for some distinct vertices $v_1, \ldots, v_r\in V(G)$.

Proof. By Lemma 3, there exist graphs $G, H$, with $H = G - \{u_1, \ldots, u_r\}, W(G) = W(H)$. By Lemma 4, there is a vertex $u\in V(G)$ with $u\notin \{u_1, \ldots, u_r\}, t_H(u) - t_G(u)\geq r$. Clearly, we can find integer $k$ with $\frac{(1+rk)r}{2}\geq t_H(u) - t_G(u)$, then by lemma 5, there is a tree $T_1$ with $|V(T_1)| = rk + 1$ and a vertex $v\in V(T_1)$ such that $t_{T_1}(v) = (t_H(u) - t_G(u))k$. By identifying $u$ with $v$, we obtain $G_1$. Then, we have $W(G_1) = W(G) + W(T_1) + (|V(T_1)|-1)t_G(u) + (|V(G)|-1)t_{T_1}(v)$, and we have:

Then, for $G_1$, take $G_1' = G_1 - \{u_1, \ldots, u_r\}$, by Lemma 4, there is a vertex $u \in V(G_1)$ with $u\notin \{u_1, \ldots, u_r\}, (t_{G_1}'(u) - t_{G_1}(u))\geq r$. By Lemma 5, there is a tree $T_2$ with $V(T_2) = rk_2 + 1$ such that there is a vertex $v\in V(T)$ with $t_{T_2}(v) = (t_{G_1'}(u)-t_{G_1}(u))k_2$. By identifying $u$ with $v$, we obtain $G_2$. Similarly, we have $W(G_2 - \{u_1, \ldots, u_r\}) = W(G_2)$. Similarly, we can obtain $G_3, G_4, \ldots$, which completes the proof.

Remark 1. For an integer $k > 0$, there exist a rational number $u = \frac{a}{b}$ and integer $n_2 > 0$ such that

$(i)$ $0 < \frac{8uk-4u+8k-8-ku^2}{4k} < \frac{1}{3}$.

$(ii)$ $n_2 \equiv 0$ (mod $4ka^2$), $0 < \omega_2 = \lambda_2n_2^2 + \lambda_1n_2 + \lambda_0 < \frac{n_2(n_2-1)}{2}, 0 < \omega_1 = \frac{n_1^2}{4} < \frac{n_1(n_1-1)}{2}$, where $n_1 = un_2 - 4$, $\lambda_2 = \frac{8uk-4u+8k-8-ku^2}{4k} = \frac{8bka - 4ba + 8ka^2 - 8a^2 + kb^2}{4ka^2}, \lambda_1 = \frac{-5k+2+u}{k} = \frac{-5ka + 2a + b}{ak}$, and $\lambda_0 = -5$

Proof. (i) Let $f_k(u) = \frac{8uk-4u+8k-8-ku^2}{4k}$. If $k = 1$, we have $f_k(4) = 0, f_k(0) = 0$. Since $f_k(u)$ is a quadratic function, there is a rational number $u$ with $0 < f_k(u) < \frac{1}{3}$. If $k > 1$, we have $f_{k}(0) = 2-\frac{2}{k} > 0$. Then there is a real number $x > 0$ with $f_k(x) = 0$. Then there is a rational number $u$ with $0 < f_k(u) < \frac{1}{3}$.

(ii) Since $0 < \lambda_2 < \frac{1}{3} < \frac{1}{2}$, we have $\lambda_2n_2^2 + \lambda_1n_2 + \lambda_0 < \frac{n_2(n_2-1)}{2}$ when $n_2$ is large enough. And clearly, we have $0 < \omega_1 = \frac{n_1^2}{4} < \frac{n_1(n_1-1)}{2}$ when $n_1$ is large enough. Now, let $n_2 \equiv 0$ (mod $4ka^2$) and large enough. Let $n_1 = un_2 - 4$. (ii) holds.

Clearly, $n_1, n_2, \omega_1, \omega_2$ all are positive integers.

Lemma 6. For an integer $k \geq 1$, let $T_1, T_2$ be two trees with $|V(T_1)| = n_1, t_{T_1}(v_1) = \omega_1, |V(T_2)| = n_2, t_{T_2}(v_2) = \omega_2$ and $G = G(T_1, T_2, k, v_1, v_2)$. Then we have $W(G) = W(G - \{w_1\}) = \ldots = W(G - \{w_k\})$.

Proof. We will only show $W(G) = W(G - \{w_1\})$. Let $G - \{w_1\} = G'$, then we have:

Since $n_1 = un_2 - 4, t_{T_2}(v_2) = \omega_2 = \lambda_2n_2^2 + \lambda_1n_2 + \lambda_0, t_{T_1}(v_1) = \omega_1 = \frac{n_1^2}{4}$, then we have:

Since $\lambda_2 = \frac{8uk-4u+8k-8-ku^2}{4k}, \lambda_1 = \frac{-5k+2+u}{k}, \lambda_0 = -5$, therefore, we have:

For example, let $b = 13, a = 2, u = \frac{13}{2}, n_1 = 2076, n_2 = 320, \omega_1 = 1077444, \omega_2 = 18955$. Let $P_{607} = v_1v_2\ldots v_{607}$ be a path with $607$ vertices, $P_{65} = u_1u_2\ldots u_{65}$ be a path with $66$ vertices. Let $S_{1234}$ be a $(1234)$-star centered at $v_{608}$ and $S_{236}$ be a $(236)$-star centered at $u_{66}$. Now we obtain $T_1$ by adding $v_{608}$ to $v_{607}$ and we obtain $T_2$ by adding $u_{66}$ to $u_{65}$.

Let $G = G(T_1, T_2, 2, v_1, u_1)$, $G' = G - \{w_1\}$.

Theorem 2. For any $k > 0$, there are infinitely many graphs $G$ for which $W(G) = W(G-\{w_1\}) = W(G - \{w_2\}) = \ldots = W(G - \{w_k\})$ for some distinct vertices $w_1, \ldots, w_k\in V(G)$.

Proof. By Remark 1, there exist rational number $u = \frac{a}{b}$ with $0 < \frac{8uk-4u+8k-8-ku^2}{4k} < \frac{1}{3}$ and an integer $n_2$ with $n_2$ (mod $4ka^2) \equiv 0$ such that $0 < \omega_2 = \lambda_2n_2^2 + \lambda_1n_2 + \lambda_0 < \frac{n_2(n_2-1)}{2}, 0 < \omega_1 = \frac{n_1^2}{4} < \frac{n_1(n_1-1)}{2}$ where $n_1 = un_2 - 4$, and $\lambda_2 = \frac{8uk-4u+8k-8-ku^2}{4k} = \frac{8bka - 4ba + 8ka^2 - 8a^2 + kb^2}{4ka^2}, \lambda_1 = \frac{-5k+2+u}{k} = \frac{-5ka + 2a + b}{ak}, \lambda_0 = -5$. Since $n_1, n_2, \omega_1, \omega_2$ all are integers such that $0 < \omega_2 < \frac{n_2(n_2-1)}{2}$ and $0 < \omega_1 < \frac{n_1(n_1-1)}{2}$, therefore there exist two trees $T_1, T_2$ with $|V(T_1)| = n_1, t_{T_1}(v_1) = \omega_1, |V(T_2)| = n_2, t_{T_2}(v_2) = \omega_2$. By Lemma 6, there is a graph $G = G(T_1, T_2, k, v_1, v_2)$ with $W(G) = W(G - \{w_1\}) = \ldots = W(G - \{w_k\})$. Let $G_{i} = G -\{w_i\}$. Clearly, we have $t_{G_1}(u) = t_{G_2}(u) = \ldots = t_{G_k}(u)$ and $t_{G_i}(u) - t_{G}(u)\geq 1$.

Clearly, there is an integer $k$ such that $\frac{(1+rk)r}{2}\geq t_{G_1}(u) - t_{G}(u)$ for any $r$. Now by Lemma 5, there is a tree $T$ with $|V(T)| = rk + 1, t_T(v) = (t_{G_1}(u) - t_{G}(u))k$, where $v\in V(T)$ and $r = 1$. Now we obtain a graph $G^2$ by identifying $u$ with $v$ from $G, T$. Let $n_G = |V(G)|, n_T = |V(T)|$. Since $W(G^2) = W(G) + W(T) + (n_G-1)t_T(v) + (n_T - 1)t_G(u), W(G^2 - \{w_i\}) = W(G_i) + W(T) + (n_G-2)t_T(v) + (n_T - 1)t_{G_i}(u)$, then we have:

Therefore, $W(G^2) = W(G^2 - \{w_1\}) = \ldots = W(G^2 - \{w_k\})$. Let $G^2_{i} = G^2 -\{w_i\}$, then we have $t_{G^2_1}(u) = t_{G^2_2}(u) = \ldots = t_{G^2_k}(u)$. Let $T_4$ be a tree with $|V(T_4)| = rk_2 + 1, t_T(v) = (t_{G^2_1}(u) - t_{G^2}(u))k_2$ where $v\in V(T_4)$ and $r = 1$. Now we obtain a graph $G^3$ by identifying $u$ with $v$ from $G^2, T_4$. Similarly, we have $W(G^3) = W(G^3 - \{w_1\}) = \ldots = W(G^3 - \{w_k\})$. Similarly, we can obtain $G^4, G^5, \ldots$. Then the proof is completed.

3.   Conclusions

Topological index is a mathematical quantity which is assigned to a graph in order to develop relationships between a graph (or structure of a molecule) and some properties including biological activity, physical properties or chemical reactivity. Due to vast applications in several branches of science, the Wiener index has remained one of the most frequently studied topological index both in pure and applied mathematics. In this paper, we are able to contribute to this topic by means of a study related to the Šoltés problem. In particular, we have solved the problem of finding infinite family of graphs $G$ such that for each $G$ there exist distinct vertices $w_1, \ldots, w_k\in V(G)$ satisfying $W(G) = W(G-\{w_1\}) = W(G - \{w_2\}) = \ldots = W(G - \{w_k\})$. The problem was posed by Knor et al. ^[4] in 2018 during the study related to Šoltés problem. The solution presented in this paper may be a step forward toward the solution of Šoltés problem and may be used by other mathematicians working in this area.

Acknowledgments

This work was supported by the Characteristics Innovation Projects of Colleges and Universities of Guangdong Province (Nos. 2019KTSCX234 and 2019KTSCX235). Moreover, all the authors are thankful to their respective institutes.

Conflict of interest

The authors declare that there are no conflicts of interest.