In this paper, we prove that, the Wiener index of a connected tripartite graph is any natural number except 1, 2, 5, 6 and 11.
Let G be a finite, connected graph with undirected edges and without loops. The vertex set and edge set of \(G\) are denoted by \(V(G)\) and \(E(G)\) respectively. The Wiener index \(W(G)\) of \(G\) is defined as \[W(G) = \frac{1}{2}\sum _{u \in V(G)} d_{G}(u),\] where the distance \(d_{G}(u)\) of a vertex \(u\) is the sum of all distances between \(u\) and all other vertices of G.
The quantity \(W(G)\) is sometimes called the Wiener number of the graph \(G,\) because it was studied by Harold Wiener [10] in connection with certain chemical applications. He observed a relationship between the boiling point of paraffin and the wiener index. Due to its basic character and applicability, it has arisen in diverse contexts, including efficiency of information, sociometry, mass transport, cryptography, theory of communication, molecular structure, computer network topology and many more.
This index, originally used in chemical graph representations of the non-hydrogen atoms of a molecule, is considered to be a fundamental and useful network descriptor.
Computing a tree that minimizes the wiener index has been studied in the area of communication networks, where it is known as the minimum routing cost spanning tree problem. The wiener index and its several variations have found applications in chemistry, for example, in predicting the antibacterial activity of drugs and modeling crystalline phenomena. It has also been used to give insight into various chemical and physical properties of molecules [9] and to correlate the structure of molecules with their biological activity. The Wiener index has become part of general scientific culture, and it is skill the subject of intensive research [1,4,5,11].
For all terms and definitions not defined specifically in this paper, we refer to [2,3]. For more conjectures and open problems in Wiener index, refer [5].
In [7] Gutman and Yeh determined the Wiener index of all connected bipartite graphs.
In this paper, we determine which values are assumed as the Wiener index of connected tripartite graphs.
Let N be the set of all natural numbers. Then the following elementary results hold, which we restate here because of completeness.
Proposition 1.1. [7] If e is an edge of the graph G and both G and \(G \setminus e\) are connected, then \[W(G) < W(G \setminus e) .\]
Proposition 1.2. [6] Among all connected graphs with n vertices, n \(\geq\) 1, the path \(P_n\) has maximal Wiener index. Also, \[W(P_{n}) = {n+1 \choose 3} .\]
Theorem 1.3. [8] Let \(\mathcal{G}\) be the set of all connected graphs. Then \[N\setminus \left\{W(G)|G \in\mathcal{G}\right\} = \left\{2, 3\right\}.\]
Theorem 1.4. [7] Let \(\mathcal{B}\) be the set of all connected, finite bipartite graphs. Then \[N \setminus \left\{W(G)|G \in\mathcal{B}\right\} = \left\{2, 3, 5, 6, 7, 11, 12, 13, 15, 17, 19, 33, 37, 39\right\}.\]
A graph G is tripartite if V(G) can be partitioned into three subsets \(V_{a}, V_{b}, V_{c}\) such that \(uv\) is an edge of \(G\) if and only if \(u\) and \(v\) belong to different partite sets.
If every two vertices in different partite sets are joined by an edge, then G is called a complete tripartite graph. It is denoted by \(K_{a,b,c}\).
Further let \(\mid V_{a}(G) \mid = a, \mid V_{b}(G) \mid = b\) and \(\mid V_{c}(G) \mid = c\). Then we say that \(G\) is a tripartite graph on \(a + b + c\) vertices.
Proposition 2.1. If the Wiener index of \(K_{a,b,c}\) is \(m,\) then the Wiener index of \(K_{a,b,c} \setminus e\) is \(m+1\) for any edge \(e\) of \(K_{a,b,c}\).
Proof. Let \(\lbrace v_1, v_2, \cdots, v_a \rbrace \cup \lbrace w_1, w_2, \cdots, w_b \rbrace \cup \lbrace u_1, u_2, \cdots, u_c \rbrace\) be the vertices of \(K_{a,b,c}.\) The edges of \(K_{a,b,c}\) are \(v_iw_j, v_iu_k, w_ju_k, 1 \leq i \leq a, 1 \leq j \leq b, 1 \leq k \leq c.\)
Then
\[\begin{aligned} W(K_{a,b,c}) &= \frac{1}{2}[a(b+c+2(a-1))+b(c+a+2(b-1))+c(a+b+2(c-1))] \\ &= a^2 +b^2+c^2 +ab+bc+ca-a-b-c \\ &= m. \end{aligned}\]
Let \(e=v_iw_j\) for some \(i\) and \(j.\) Then
\[\begin{aligned} W(K_{a,b,c} \setminus e) =& \frac{1}{2}\lbrace[(a-1)(b+c+2(a-1))+(b-1+c+2(a-1)+2)] \\ & + [(b-1)(c+a+2(b-1))+(a-1+c+2(b-1)+2)] \\ & +c(a+b+2(c-1))\rbrace \\ =& a^2 +b^2+c^2 +ab+bc+ca-a-b-c+1 \\ =& m+1. \end{aligned}\] ◻
Example 2.2.
In \(K_{2,2,3}, W(K_{2,2,3})= 26\) and \(W(K_{2,2,3} \setminus u_2v_1)=27.\)
Lemma 2.3. If G is a connected tripartite graph on a + b + c vertices, then \[\label{eq:1} W(G) \geq (a + b + c) (a + b + c – 1) – ab – bc – ca , \tag{1}\] with equality only if G = \(K_{a,b,c}\).
Proof. Observe that the right hand side of (1) is just W(\(K_{a,b,c}\)). Every other tripartite graph on a + b + c vertices is obtained by deleting one or more edges from \(K_{a,b,c}\). This lemma follows from Proposition 1.1. ◻
Lemma 2.4. If G is a connected tripartite graph on n vertices, n \(\geq\) 3, then \[W(G) \geq \begin{cases} n(n-1)- \frac{n^{2}}{3} & \text{if n $ \equiv $ 0 (mod 3)}, \\ n(n-1)- \frac{n^{2}-1}{3} & \text{if n $\equiv\pm$ 1 (mod 3)} . \end{cases}\]
Proof. This lemma is a corollary of Lemma 2.3 because \(n = a + b + c.\) Also, \[\label{eq:2} ab+ bc +ca = \frac{1}{6} [2(a+b+c)^2-(a-b)^2-(b-c)^2-(c-a)^2]. \tag{2}\]
When \(n= a+b+c \equiv 0(mod \hspace{0.3cm}3),\) the right hand side of 2 is \(\leq \frac{n^2}{3}\) and when \(n \equiv \pm 1(mod \hspace{0.3cm} 3),\) the right hand side of 2 is \(\leq \frac{n^2-1}{3}\). ◻
For the first few values of n, the minimal and maximal values of W of connected tripartite graphs on n vertices are given as Table 1.
| n | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| \(W_min\) | 3 | 7 | 12 | 18 | 26 | 35 | 45 | 57 | 70 | 84 |
| \(W_max\) | 4 | 10 | 20 | 35 | 56 | 84 | 120 | 165 | 220 | 286 |
Let \(G_{a,b,c}\) be the null graph on the vertex set \(\{v_{1}, v_{2}, \ldots, v_{a}, w_{1}, w_{2}, \ldots, w_{b}, u_{1}, u_{2}, \ldots, u_{c}\}\). Assuming that \(a \geq 1\) and \(1 \leq l \leq k \leq j \leq i \leq a\). Construct now the tripartite graphs \(G_{a, 2, 1}(i)\), \(G_{a, 3, 2}( i, j )\),\(G_{a, 4, 3}(i, j, k)\) and \(G_{a, 5, 4}(i, j, k, l )\) as follows. The graph \(G_{a, 2, 1}(i)\) is obtained from \(G_{a, 2, 1}\) by connecting \(w_{r}\) with \(v_{1}, v_{2}, \ldots, v_{a}\), r = 1, 2 and \(u_{1}\) with \(v_{1}, v_{2}, \ldots, v_{i}\). The graph \(G_{a, 3, 2}( i, j )\) is obtained from \(G_{a, 2, 1}(i)\) by introducing two new vertices \(w_{3}\) and \(u_{2}\) and edges \(w_{3}v_{r}, 1 \leq r \leq a\) and \(u_{2}v_{s}\) , \(1 \leq s \leq j .\) The graph \(G_{a, 4, 3}(i, j, k)\) is obtained from \(G_{a, 3, 2}( i, j )\) by introducing two new vertices \(w_{4}\) and \(u_{3}\) and edges \(w_{4}v_{r}\) , \(1 \leq r \leq a\) and \(u_{3}v_{s}\) , \(1 \leq s \leq k.\) The graph \(G_{a, 5, 4}(i, j, k, l )\) is obtained from \(G_{a, 4, 3}(i, j, k)\) by introducing two new vertices \(w_{5}\) and \(u_{4}\) and edges \(w_{5}v_{r}\) , \(1 \leq r \leq a\) and \(u_{4}v_{s}\) , \(1 \leq s \leq l.\)
Lemma 2.5. \[\ W\left(G_{a, 2, 1} (i)\right) = a^{2} + 4a + 6 – 2i , \tag{3}\] \[W\left(G_{a, 3, 2}(i, j )\right) = a^{2} + 8a + 20 – 2(i + j), \tag{4}\] \[W\left(G_{a, 4, 3}(i, j, k)\right) = a^{2} + 12a + 42 – 2(i + j+ k), \tag{5}\] \[W\left(G_{a, 5, 4}(i, j, k, l)\right) = a^{2} + 16a + 72 – 2(i + j+ k + l). \tag{6}\]
Proof. Consider \(G_{a,2}(i).\) Here \[\begin{split} d(u_1) & =i+3(a-i)+4, \\ d(w_1) & = d(w_2) = a + 2 + 2 ,\\ d(v_1) & =d(v_2) = \cdots = d(v_i) = 3+2(a-1), \hspace{0.1cm} and \\ d(v_{i+1}) & = d(v_{i+2}) = \cdots = d(v_a) = 2(a-1)+5. \end{split}\]
Therefore, \[\begin{split} W(G_{a,2}(i)) =& \frac{1}{2}[i+3a-3i+4+2(a+4)+i(3+2a-2) +(a-i)(2a-2+5)\\ =& a^2+4a+6-2i. \end{split}\]
The remaining results can be easily verified in this manner. ◻
It is easy to verify that for a = 1, 2, 3, \(\ldots , W(G_{a, 5, 4}(i, j, k, l))\) takes all possible natural numbers, except the 121 values listed below.
Lemma 2.6. Let \(\mathcal{G}_{5,4}\) be the set of all graphs \(G_{a, 5, 4}(i, j, k, l ), a \geq 1.\) Then \[\begin{aligned} N \setminus \left\{W(G)|G \in\mathcal{G}_{5,4}\right\} =& \{ 1, 2, \cdots , 80, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 93, 95, 97, 99,\\ & 101, 102, 103, 104, 106, 108, 110, 112, 114, 116, 118, 123, 125, 127, \\ & 129, 131, 133, 135, 146, 148, 150, 152, 154, 171, 173, 175, 198 \}. \end{aligned}\]
Proof. \(W(G_{a,5,4}(i,j,k,l)) \equiv 1(mod \hspace{0.3cm} 2)\) if and only if \(a \equiv 1(mod \hspace{0.3cm} 2).\)
Also, \[\lbrace W(G_{a,5,4}(i,j,k,l))/1 \leq i \leq j \leq k \leq l \leq a \rbrace = \lbrace a^2+8a+72, a^2 +8a +74, \cdots , a^2 + 16a +64 \rbrace,\] where the minimum is obtained when \(i=j=k=l=a\) and maximum is obtained when \(i=j=k=l=1.\)
Further \(W(G_{a,5,4}(1,1,1,1))-W(G_{a+2,5,4}(a+2, a+2,a+2,a+2))= 4a-28 \geq 0\) for \(a\geq7.\)
Thus all odd numbers \(177(= W(G_{7,5,4}(7,7,7,7)))\), 179, 181 , \(\cdots,\) and all even numbers \(200 (=W(G_{8,5,4}(8,8,8,8)))\), 202, 204, \(\cdots,\) are Wiener indices of some \(W(G_{a,5,4}(i,j,k,l)).\)
Also, \[\begin{aligned} W(G_{1,5,4}(i,j,k,l)) =& 81,\\ W(G_{2,5,4}(i,j,k,l)) \in& \lbrace 92, 94, 96,98, 100 \rbrace,\\ W(G_{3,5,4}(i,j,k,l)) \in& \lbrace 105, 107, 109, 111, 113, 115, 117,119,121 \rbrace,\\ W(G_{4,5,4}(i,j,k,l)) \in& \lbrace 120,122,124, 126, 128, 130, 132, 134, 136, 138, 140, 142, 144 \rbrace ,\\ W(G_{5,5,4}(i,j,k,l)) \in& \lbrace 137, 139, 141, 143, 145, 147, 149, 151, 153, 155, 147, 159, 161, 163, 165, \\ & 167, 169 \rbrace,\\ W(G_{6,5,4}(i,j,k,l)) \in& \lbrace 156, 158, 160, 162, 164, 166, 168, 170, 172, 174, 176, 178, 180, 182, 184,\\& 186, 188, 190, 192, 194, 196 \rbrace. \end{aligned}\]
Thus, \[\begin{aligned} N \setminus \left\{W(G)|G \in\mathcal{G}_{5,4}\right\} =& \{ 1, 2, \cdots , 80, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 93, 95, 97, 99,\\ & 101, 102, 103, 104, 106, 108, 110, 112, 114, 116, 118, 123, 125, 127, \\ & 129, 131, 133, 135, 146, 148, 150, 152, 154, 171, 173, 175, 198 \}. \end{aligned}\] ◻
Let, further \(\mathcal{G}_{2,1},\mathcal{G}_{3,2},\mathcal{G}_{4,3}\)
be the sets of all graphs \(G_{a, 2, 1}(i),
G_{a, 3, 2}( i, j )\) and \(G_{a, 4,
3}(i, j, k)\) respectively. Then a direct calculation, based on
(3), (4) and (5)
shows that \(9, 14,16, 21,\) 23, 25,
30, 32, 34, 36, 41, 43, 45, 47, 49, 54, 56, 58, 60, 62, 64, 69, 71, 73,
75, 77, 79, 86, 88, 90 \(\in\{W(G)|G
\in\mathcal{G}_{2,1}\}\) and 52, 65, 67, 80, 82, 84, 97, 99, 101,
103, 116, 118 \(\in\{W(G)|G
\in\mathcal{G}_{3,2}\}.\)
From these observations combined with Lemma 2.6, we see that
all numbers in the set \[\begin{aligned} N
\setminus \{& 1, 2, 3, 4, 5,6, 7, 8, 10, 11, 12, 13, 15, 17, 18,
19, 20, 22, 24, 26, 27. 28. 29, 31, 33, 35, 37, 38, 39, 40, 42,\\&
44, 46, 48, 50, 51, 53,55, 57, 59, 61, 63, 66, 68, 70, 72, 74, 76, 78,
83, 85, 87,89, 91, 93, 95,102, 104,\\& 106, 108, 110, 112, 114,123,
125, 127, 129, 131, 133, 135, \\& 146, 148, 150, 154, 171, 173,
175, 198\},\end{aligned}\] are the Wiener indices of connected
tripartite graphs \(G_{a, 2, 1}(i)\),
\(G_{a, 3, 2}( i, j )\), \(G_{a, 4, 3}(i, j, k)\) and \(G_{a, 5, 4}(i, j, k, l )\).
The Wiener indices of complete tripartite graphs \(K_{a,b,c}\) for few values of a, b, c are given as Table 2.
If we delete one edge from complete tripartite graph, then the Wiener index of the new graph increases by one as that of the Wiener index of the complete tripartite graph.
In this way, we obtained the numbers 8, 22, 29, 38, 40, 44, 50, 53, 68, 89, 127, 173 as the Wiener indices of graphs obtained from complete tripartite graph by deleting one edge.
| a | b | c | W(\(K_a,b,c\)) | a | b | c | W(\(K_a,b,c\)) |
| 1 | 1 | 1 | 3 | 6 | 4 | 1 | 76 |
| 2 | 1 | 1 | 7 | 7 | 2 | 2 | 78 |
| 2 | 2 | 1 | 12 | 5 | 4 | 3 | 85 |
| 3 | 1 | 1 | 13 | 5 | 5 | 2 | 87 |
| 2 | 2 | 2 | 18 | 6 | 5 | 1 | 91 |
| 3 | 2 | 1 | 19 | 7 | 4 | 1 | 93 |
| 3 | 2 | 2 | 26 | 6 | 4 | 3 | 102 |
| 3 | 3 | 1 | 27 | 6 | 5 | 2 | 104 |
| 4 | 2 | 1 | 28 | 7 | 4 | 2 | 106 |
| 5 | 1 | 1 | 31 | 6 | 6 | 1 | 108 |
| 3 | 3 | 2 | 35 | 8 | 3 | 2 | 110 |
| 4 | 3 | 1 | 37 | 8 | 4 | 1 | 112 |
| 5 | 2 | 1 | 39 | 7 | 5 | 2 | 123 |
| 4 | 3 | 2 | 46 | 8 | 3 | 3 | 125 |
| 4 | 4 | 1 | 48 | 8 | 5 | 1 | 129 |
| 4 | 3 | 3 | 57 | 9 | 3 | 2 | 131 |
| 5 | 3 | 2 | 59 | 9 | 4 | 1 | 133 |
| 5 | 4 | 1 | 61 | 5 | 5 | 5 | 135 |
| 6 | 3 | 1 | 63 | 8 | 6 | 1 | 148 |
| 4 | 4 | 3 | 70 | 10 | 3 | 2 | 154 |
| 5 | 4 | 2 | 72 | 9 | 6 | 1 | 171 |
| 6 | 3 | 2 | 74 | 10 | 5 | 1 | 175 |
| 6 | 6 | 6 | 198 |
From Proposition 1.2, we have W(\(P_{3}\)) = 4, W(\(P_{4}\)) = 10, W(\(P_{5}\)) = 20. Also,
\(W( K_{2,2,1}\verb|\ |{v_{1}w_{1}, v_{1}w_{2}, v_{2}w_{1}}) = 15,\)
\(W(K_{2,2,1}\verb|\ |{v_{1}w_{1}, v_{1}u_{1}, w_{2}u_{1}}) = 17,\)
\(W(K_{2,2,2}\verb|\ |{v_{1}w_{1}, v_{1}w_{2}, v_{1}u_{1}, v_{2}w_{1}, v_{2}w_{2}}) = 24,\)
\(W(K_{3,2,2}\verb|\ |{v_{1}w_{1}, v_{1}w_{2}, v_{1}u_{1}, v_{2}w_{1}, v_{2}w_{2}, v_{3}w_{1}}) = 33,\)
\(W(K_{3,3,2}\verb|\ |{v_{1}w_{1}, v_{1}w_{2}, v_{1}w_{3}, v_{1}u_{1}, v_{2}w_{1}, v_{2}w_{2}}) = 42,\)
\(W(K_{3,3,3}\verb|\ |{v_{1}w_{1}, v_{1}w_{2}, v_{1}w_{3}, v_{1}u_{1}, v_{2}w_{1}}) = 51,\)
\(W(K_{3,3,3}\verb|\ |{v_{1}w_{1}, v_{1}w_{2}, v_{1}w_{3}, v_{1}u_{1}, v_{2}w_{1} ,v_{2}w_{2}, v_{2}w_{3}}) = 55,\)
\(W(K_{4,3,3}\verb|\ |{v_{1}w_{1}, v_{1}w_{2}, v_{1}w_{3}, v_{1}u_{1}, v_{1}u_{2} ,v_{2}w_{1}, v_{2}w_{2}}) = 66,\)
\(W(K_{7,3,1}\verb|\ |{v_{1}w_{1}, v_{1}w_{2}, v_{1}w_{3}, v_{2}w_{1}}) = 83,\)
\(W(K_{7,4,1}\verb|\ |{v_{1}w_{1}, v_{1}w_{2}}) = 95,\)
\(W(K_{8,4,1}\verb|\ |{v_{1}w_{1}, v_{1}w_{2}}) = 114,\)
\(W(K_{7,6,2}\verb|\ |{v_{1}w_{1}, v_{1}w_{2}, v_{1}w_{3}, v_{1}w_{4}}) = 146,\)
\(W(K_{7,7,1}\verb|\ |{v_{1}w_{1}, v_{1}w_{2}, v_{1}w_{3}}) = 150,\)
\(W(K_{7,7,1}\verb|\ |{v_{1}w_{1}, v_{1}w_{2}, v_{1}w_{3}, v_{1}w_{4}, v_{1}w_{5}}) = 152.\)
Thus, there exists tripartite graphs with Wiener indices being equal to any natural numbers except 1, 2, 5, 6 and 11.
Theorem 2.7. Let \(\mathfrak{T}\) be the set of all finite, connected tripartite graphs. Then \(N\verb|\ |\{W(G) \verb||| G \in\mathfrak{T}\} = \{1, 2, 5, 6, 11\}.\)
Proof. It remains to verify that the five numbers 1, 2, 5, 6, 11 cannot be the Wiener indices of any tripartite graphs.
Case 1.W = 1, 2, 5, 6.
Because of Lemma 2.4, tripartite graphs for which W \(<\) 7 must have less than four vertices. There are exactly two connected tripartite graphs with less than four vertices and by direct verification, we conclude that their Wiener indices are not equal to 1, 2, 5 or 6.
Case 2. W = 11.
Because of Lemma 2.4, tripartite graphs for which W \(<\) 12 must have less than five vertices. On the other hand Proposition 1.2 implies that the maximal possible Wiener indices of such graph is \(W(P_{4})\) = 10. Consequently, W cannot have the value 11.
By this, we showed that none of the numbers 1, 2, 5, 6 and 11 is the Wiener index of a tripartite graph.
This completes the proof of Theorem 2.7 . ◻
We thank the anonymous referee for both the careful reading and suggestions.