INFORMATION MENU
Full-Text PDF

Open Journal of Discrete Applied Mathematics

Vol. 2 (2019), Issue 3, pp. 19 – 22
ISSN: 2617-9687 (Online) 2617-9679 (Print)
DOI: 10.30538/psrp-odam2019.0019

Wiener index of uniform hypergraphs induced by trees

Andrey Alekseevich Dobrynin\(^1\)
Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk, 630090, Russia.; (A.A.D)
\(^{1}\)Corresponding Author: dobr@math.nsc.ru
Copyright © 2019 Andrey Alekseevich Dobrynin. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Received: September 5, 2019 – Accepted: October 23, 2019 – Published: November 2, 2019

Abstract

The Wiener index \(W(G)\) of a graph \(G\) is defined as the sum of distances between its vertices. A tree \(T\) generates \(r\)-uniform hypergraph \(H_{r,k}(T)\) by the following way: hyperedges of cardinality \(r\) correspond to edges of the tree and adjacent hyperedges have \(k\) vertices in common. A relation between quantities \(W(T)\) and \(W(H_{r,k}(T))\) is established.

Keywords:

Tree, hypergraph, Wiener index.

1. Introduction

In this paper we are concerned with undirected connected graphs \(G\) with vertex set \(V(G)\) and edge set \(E(G)\). The degree of a vertex is the number of edges that are incident to the vertex. Degree of a vertex \(v\) is denoted by \(\deg(v)\). If \(u\) and \(v\) are vertices of \(G\), then the number of edges in a shortest path connecting them is said to be their distance and is denoted by \(d_G(u,v)\). Distance of a vertex \(v\) is the sum of distances from \(v\) to all vertices of a graph, \(d_G(v)=\sum_{u\in V(G)} d(v,u)\). The Wiener index is a graph invariant defined as the sum of distances between all vertices of \(G\): $$ W(G)= \sum_{u,v \in V(G)} d(u,v)=\frac12 \sum_{v \in V(G)} d_G(v). $$

It was introduced as a structural descriptor for tree-like molecular graphs [1]. Details on the mathematical properties and chemical applications of the Wiener index can be found in books [2, 3, 4, 5, 6, 7] and reviews [8, 9, 10, 11, 12, 13]. A number of articles are devoted to comparing of the index of a graph and its derived graphs such as the line graph, the total graph, thorny and subdivision graphs of various kind (see, for example, [14, 15, 16, 17]). Hypergraphs generalize graphs by extending the definition of an edge from a binary to an \(r\)-ary relation. Wiener index of some classes of hypergraphs was studied in [18, 19, 20]. Chemical applications of hypergraphs were discussed in [21, 22].

Define a class of \(r\)-uniform hypergraphs \(H_{r,k}(T)\) induced by \(n\)-vertex trees \(T\). Edges of a tree correspond to hyperedges of cardinality \(r\) and adjacent hyperedges have \(k\) vertices in common, \(1 \leq k \leq \lfloor r/2\rfloor\). Examples of a tree and the corresponding hypergraph are shown in Figure 1. The number of vertices of \(H_{r,k}(T)\) is equal to \((n-2)(r-k)+r\). We are interesting in finding a relation between quantities \(W(T)\) and \(W(H_{r,k}(T))\).

Figure 1. Tree \(T\) and the induced hypergraph \(H_{7,2}(T)\).

2. Main result

Wiener indices of a tree and its induced hypergraph satisfy the following relation.

Theorem 1. For the induced hypergraph \(H_{r,k}(T)\) of a tree \(T\) with \(n\) vertices, $$ W(H_{r,k}(T)) = (r-k)^2\,W(T) + n\binom{k}{2} - (n-1)\binom{r-2k+1}{2}. $$

This result may be useful for ordering of Wiener indices of hypergraphs. If \(r\) and \(k\) are fixed, then the ordering of the Wiener index of induced hypergraphs \(H_{r,k}\) for \(n\)-vertex trees is completely defined by the ordering of the index of trees. In particular, $$ W(H_{r,k}(S_n)) \le W(H_{r,k}(T)) \le W(H_{r,k}(P_n)) $$ for any \(n\)-vertex tree \(T\), where \(S_n\) and \(P_n\) are the star and the path with \(n\) vertices, $$ W(H_{r,k}(S_n)) = \big( r(n-1)[2n(r - 2k) + 8k - 3r - 1] + k(n-2)[k(2n-3)+1] \big) /2, $$ $$ W(H_{r,k}(P_n)) = n(r-k)[(r-k)n^2 + 10k -4r-3]/6 + 2k^2-k(2r+1)+ r(r+1)/2. $$

3. Proof of Theorem 1.

The edge subdivision operation for an edge \((x,y)\in E(G)\) is the deletion of \((x,y)\) from graph \(G\) and the addition of two edges \((x,v)\) and \((v,y)\) along with the new vertex \(v\). Vertex \(v\) is called the subdivision vertex. Denote by \(T_e\) the tree obtained from the subdivision of edge \(e\) in a tree \(T\). The distance \(d_G(v,U)\) from a vertex \(v \in V(G)\) to a vertex subset \(U \subseteq V(G)\) is defined as \(d_G(v,U)=\sum_{u\in U} d_G(v,u)\).

Lemma 2. Let \(T_{e_1}, T_{e_2}, \dots , T_{e_{n-1}}\) be trees obtained by subdivision of edges \(e_1, e_2, \dots, e_{n-1}\) of \(n\)-vertex tree \(T\) with subdivision vertices \(v_1, v_2, \dots , v_{n-1}\), respectively. Then $$ d_{T_{e_1}}(v_{1}) + d_{T_{e_2}}(v_{2}) + \dots + d_{T_{e_{n-1}}}(v_{{n-1}}) = 2W(T). $$

Proof. Let \(v\) be the subdivision vertex of edge \(e=(x,y)\) of a tree \(T\). Denote by \(V_x\) and \(V_y\) the sets of vertices of two connected components after deleting edge \(e\) from \(T\) where \(x \in V_x\) and \(y \in V_y\). Since \(d_T(x)=d_T(x,V_x) + |V_y| + d_T(y,V_y)\) and \(d_T(y)=d_T(y,V_y) + |V_x| + d_T(x,V_x)\), \(d_T(x,V_x) + d_T(y,V_y) = (d_T(x) + d_T(y) - n)/2\). Then \begin{eqnarray*} d_{T_e}(v) & = & \sum_{u \in V_x} [\,d_{T_e}(v,x) + d_{T}(x,u)\,] + \sum_{u \in V_y} [\,d_{T_e}(v,y) + d_{T}(y,u)\,] \\ & = & d_T(x,V_x) + d_T(y,V_y) + n = (d_T(x) + d_T(y) + n)/2. \end{eqnarray*} Klein et al. [23] proved that \(\sum_{v \in V(T)} \deg(v) d_T(v) = 4W(T) - n(n-1)\) for an arbitrary \(n\)-vertex tree \(T\). Then \begin{eqnarray*} 2\sum_{i =1}^{n-1} d_{T_{e_i}}(v_i) & = & \sum_{(x,y) \in E(T)} (d_T(x) + d_T(y) + n) \\ &= & \sum_{v \in V(T)} \deg(v) d_T(v)+n(n-1) = 4W(T). \\[-10mm] \end{eqnarray*}

For convenience, we assume that pendent hyperedges are also adjacent with fictitious hyperedges shown by dashed lines in Figure 2. Denote by \(B_i\), \(i=1,2,\dots n\), the vertices of a hypergraph \(H=H_{r,k}(T)\) belonging to hyperedge intersections and let \(A = V(H) \setminus B_1 \cup B_2 \cup \dots \cup B_n\). We assume that edge \(E_i\) of the induced hypergraph corresponds to edge \(e_i\) of the source tree \(T\), \(i=1,2,\dots ,n-1\). Let \(d_G(U)=\sum_{u\in U} d_G(u)\) for \(U \subseteq V(G)\). Then the Wiener index of \(H\) can be represented as follows:
\begin{eqnarray} \label{General} W(H) & = & \frac{1}{2} \left( \sum_{i=1}^{n-1} d_H(E_i \cap A) + \sum_{i=1}^{n} d_H(B_i) \right). \end{eqnarray}
(1)

Figure 2. The hyperedges shown by dashed lines

Let \(u\in E_i \cap A\) and \(v_i\) be the subdivision vertex of edge \(e_i\) in \(T\), \(i=1,2,\dots ,n-1\). Then \begin{eqnarray*} d_H(u) & = & (r-2k-1) + k + k + 2(r-k)+ \dots + 2(r-k) + 3(r-k)+ \dots + 3(r-k) + \dots \\ & = & (r-2k-1) - 2(r-2k) + (r-k) + (r-k) + 2(r-k)+ \dots + 2(r-k) \\ & & \mbox{} + 3(r-k)+ \dots + 3(r-k) + 4(r-k)+ \dots + 4(r-k) + \dots \\ & = & (r-k)d_{T_{e_i}}(v_i) - 2(r-2k) + (r-2k-1). \end{eqnarray*} Summing this equality for all vertices of intersection \(E_i \cap A\), we have \(d_H(E_i \cap A)=(r-2k)d_H(u)=(r-2k)[(r-k)d_{T_{e_i}}(v_i) -(r-2k+1)]\). Applying Lemma 1, we can write
\begin{eqnarray} \label{WA} \nonumber \sum_{i=1}^{n-1} d_H(E_i \cap A) & =& (r-2k)\left( (r-k)\sum_{i=1}^{n-1} d_{T_{e_i}}(v_i) - (n-1)(r-2k+1)\right) \\[1mm] & = & (r-2k)\left[ \, 2(r-k)W(T) - (n-1)(r-2k+1) \, \right] . \end{eqnarray}
(2)
Let \(u\in B_i\) and vertex \(v_i\) of \(T\) corresponds to this hyperedge intersection, \(i=1,2,\dots ,n\). Then \begin{eqnarray*} d_H(u) & = & (k-1) + (r-k)+ \dots + (r-k) + 2(r-k) + \dots + 2(r-k) + 3(r-k)+ \dots + 3(r-k) + \dots \\ & = & (r-k)d_T(v_i) + (k-1). \end{eqnarray*} Summing this equality for all vertices of the hyperedge intersection \(B_i\), we have \(d_H(B_i)=k d_H(u)=k[\, (r-k)d_T(v_i) + (k-1)\, ]\). For vertices of all intersections,
\begin{equation} \label{WB} \sum_{i=1}^{n} d_H(B_i) = k\, [\, (r-k)\sum_{i=1}^{n} d_T(v_i) + n(k-1)\, ] = 2k(r-k)W(T) + nk(k-1). \end{equation}
(3)
Substitution expressions (2) and (3) back into Equation (1) completes the proof.

Acknowledgments

This work is supported by the Russian Foundation for Basic Research(project numbers 19-01-00682 and 17-51-560008).

Author Contributions

All authors contributed equally to the writing of this paper. All authors read and approved the final manuscript.

Conflicts of Interest:

The authors declare no conflict of interest.

References

  1. Wiener, H. (1947). Structural determination of paraffin boiling points. Journal of the American Chemical Society, 69(1), 17-20. [Google Scholor]
  2. Balaban, A. T., Motoc, I., Bonchev, D., & Mekenyan, O. (1983). Topological indices for structure-activity correlations. In Steric effects in drug design (pp. 21-55). Springer, Berlin, Heidelberg.[Google Scholor]
  3. Gutman, I., & Furtula, B. (Eds.) (2012). Distance in Molecular Graphs Theory. Mathematical chemistry monographs, 12, Univ. Kragujevac, Kragujevac, Serbia.[Google Scholor]
  4. Gutman, I., & Furtula, B. (Eds.) (2012). Distance in Molecular Graphs Applications. Mathematical chemistry monographs, 13, Univ. Kragujevac, Kragujevac, Serbia.
  5. Gutman, I., & Polansky, O. E. (1986).Mathematical Concepts in Organic Chemistry, Springer--Verlag, Berlin.[Google Scholor]
  6. Todeschini, R., & Consonni, V. (2008). Handbook of molecular descriptors (Vol. 11). John Wiley & Sons.[Google Scholor]
  7. Trinajstić, N. (1992). Chemical Graph Theory. CRC Press, Boca Raton. [Google Scholor]
  8. Dobrynin, A. A., Entringer, R., & Gutman, I. (2001). Wiener index of trees: theory and applications. Acta Applicandae Mathematica, 66(3), 211-249. [Google Scholor]
  9. Dobrynin, A. A., Gutman, I., Klavžar, S., & Žigert, P. (2002). Wiener index of hexagonal systems. Acta Applicandae Mathematica, 72(3), 247-294.[Google Scholor]
  10. Nikolić, S., & Trinajstić, N. (1995). The Wiener index: Development and applications. Croatica Chemica Acta, 68(1), 105-129.[Google Scholor]
  11. Entringer, R. C., Jackson, D. E., & Snyder, D. A. (1976). Distance in graphs. Czechoslovak Mathematical Journal, 26(2), 283-296.[Google Scholor]
  12. Knor, M., Škrekovski, R., & Tepeh, A. (2015). Mathematical aspects of Wiener index. Ars Mathematica Contemporanea, 11(2), 327--352.[Google Scholor]
  13. Entringer, R. C. (1997). Distance in graphs: trees. Journal of combinatorial mathematics and combinatorial computing , 24, 65--84.[Google Scholor]
  14. Eliasi, M., Raeisi, G., & Taeri, B. (2012). Wiener index of some graph operations. Discrete Applied Mathematics, 160(9), 1333-1344. [Google Scholor]
  15. Gutman, I. (1998). Distance of thorny graphs. Publications de l'Institut Mathématique (Beograd), 63(31-36), 73-74. [Google Scholor]
  16. Knor, M., & Škrekovski, R. (2014). Wiener index of line graphs. In Quantitative Graph Theory: Mathematical Foundations and Applications, 279-301. 279--301. [Google Scholor]
  17. Dobrynin, A. A., & Mel'nikov, L. S. (2012). Wiener index of line graphs. In: Distance in Molecular Graphs Theory, Gutman, I., \& Furtula, B. (Eds.). Univ. Kragujevac, Kragujevac, Serbia, 85--121. [Google Scholor]
  18. Guo, H., Zhou, B., & Lin, H. (2017). The Wiener index of uniform hypergraphs. MATCH Communications in Mathematical and in Computer Chemistry, 78, 133-152.[Google Scholor]
  19. Rani, L. N., Rajkumari, K. J., & Roy, S. (2019). Wiener Index of Hypertree. In Applied Mathematics and Scientific Computing (pp. 497-505). Birkhäuser, Cham.[Google Scholor]
  20. Sun, L., Wu, J., Cai, H., & Luo, Z. (2017). The Wiener index of \(r\)-uniform hypergraphs. Bulletin of the Malaysian Mathematical Sciences Society, 40(3), 1093-1113.[Google Scholor]
  21. Konstantinova, E. V., & Skorobogatov, V. A. (2001). Application of hypergraph theory in chemistry. Discrete Mathematics, 235(1-3), 365-383. [Google Scholor]
  22. Konstantinova, E. (2000). Chemical hypergraph theory. Lecture Notes from Combinatorial & Computational Mathametics Center, http://com2mac. postech. ac. kr. [Google Scholor]
  23. Klein, D. J., Mihalić, Z., Plavšić, D., & Trinajstić, N. (1992). Molecular topological index: A relation with the Wiener index. Journal of chemical information and computer sciences, 32(4), 304-305. [Google Scholor]
Category: ODAM - Vol 2 - Issue 3 (2019)