The cut method on hypergraphs for the Wiener index

Abstract

The cut method has been proved to be extremely useful in chemical graph theory. In this paper the cut method is extended to hypergraphs. More precisely, the method is developed for the Wiener index of k-uniform partial cube-hypergraphs. The method is applied to cube-hypergraphs and hypertrees. Extensions of the method to hypergraphs arising in chemistry which are not necessary k-uniform and/or not necessary linear are also developed.

1 Introduction

The cut method, whose standard form was introduced in 1995 in [19], has had a remarkable response in chemical graph theory. The method originally designed for the Wiener index of partial cubes was later developed for many other topological indices and has undergone many generalizations to more general situations than partial cubes. This applies in itself to many applications in mathematical chemistry where topological indices play important role. The basic idea is to first find a partition of the edges of a (molecular) graph and by removing parts of this partition construct smaller (weighted) graphs, called quotient graphs. After that, we infer back to the original graph from the quotient graphs. The state of research on the cut method up to 2015 is summarized in the survey article [18]. The method is still the subject of ongoing research, see [1, 3, 4, 6, 11, 31, 32] as well as references therein.

Hypergraphs form a structure that greatly generalizes the concept of a graph. In chemical graph theory, the standard method of representing molecules is by means of associated (chemical) graphs. However, some molecules are more complicated than others and sometimes it is more convenient and more adequate to represent them as hypergraphs, see [14, 21] for some chemical problems dealing with hypergraph theory. As a result, various problems of importance in mathematical chemistry have been investigated on hypergraphs, including spectral aspects [2, 24, 29] and different topological indices [33, 34]. Very recently, while investigating molecular representations in drug design, a hypergraph-based topological framework was designed to characterize molecular structures and interactions at atomic level [26]. Interestingly, in the very same year when the cut method was introduced, Burosch and Ceccherini published the paper [7] on isometric embeddings into hypergraphs, which is the second main source for the present paper.

The Wiener index is one of the most researched topics in the whole field of chemical graph theory. As already mentioned, the cut method was first designed for the Wiener index of graphs. In the last few years, the Wiener index has received a lot of attention also on hypergraphs. In [30] the authors investigate, among others, 3-uniform paths and lower bounds on the Wiener index of k-uniform hypergraphs. In [12, 22] hypergraphs are constructed from trees and their Wiener index investigated. The effect of some transformations on the Wiener index of a hypergraph and extremal hypertrees with respect to the Wiener index is studied in [25]. The k-uniform unicyclic hypergraphs with maximum/minimum and second maximum/minimum Wiener index are determined in [35], while the Wiener index of some composite hypergraphs and sunflower hypergraphs is the topic of [5]. Finally, in [8] the concept of the k-Wiener index is introduced and studied on the so called k-plex hypergraphs, while in [36] the maximum possible Wiener index of a connected n-vertex k-uniform hypergraph has been determined and the extremal graphs characterized.

We proceed as follows. In the next section we introduce the mathematical machinery on hypergraphs needed latter on. In particular, partial cube-hypergraphs are defined and their characterizations recalled. In Sect. 3 we develop the cut method for the Wiener index of a hypergraph. In the last section we provide applications and extensions of the cut method including cube-hypergraphs, hypertrees, and the so called linear phenylene hypergraphs.

2 Preliminaries

In this section, we set the scene for the hypergraph cut method. In the first part, we introduce the necessary concepts about hypergraphs, focusing on distance and their Cartesian products. We then introduce partial cube-hypergraphs on which the cut method will operate and recall two of their characterizations.

2.1 Hypergraphs

A hypergraph $H=(V(H),E(H))$ has the vertex set V(H) and the edge set E(H), where each edge $e \in E(H)$ is a non-empty subset of V(H). H is k-uniform if the size of every edge $e \in E(H)$ is k and is linear if $|e \cap e'| \le 1$ for every $e,e' \in E(H)$, $e \ne e'$. Let H and $H'$ be hypergraphs. If $V(H') \subseteq V(H)$ and $E(H') \subseteq E(H)$ we say that $H' \subseteq H$ is a subhypergraph of H. Clearly, if H is k-uniform, then $H'$ is also k-uniform. If $F \subseteq E(H)$, then $H - F$ denotes the subhypergraph of H obtained from H by removing all the edges from F.

Let u and v be different vertices of H. A u, v-path of length $s \ge 1$ in H is a sequence $u_0 = u, e_1, u_1, \ldots , e_s, u_{s} = v$, where $u_i$ are pairwise different vertices, $e_i$ are pairwise different edges, and $\{u_{i-1}, u_i \} \subseteq e_i$ for $i \in [s] = \{1,\ldots , s\}$. The distance $d_H(u, v)$ between vertices u and v is the length of a shortest u, v-path. We also set $d_H(u,u) = 0$. A subhypergraph $H' \subseteq H$ is isometric if $d_{H'}(u,v) = d_H(u,v)$ holds for all $u,v \in V(H')$. We further say that a set of vertices $X \subseteq V(H)$ is convex in H if for every $u,v \in X$ and every $z \in V(H)$, the equality $d_H(x,z) + d_H(z, y) = d_H(x,y)$ implies $z \in X$. The Wiener index of a hypergraph H is defined as the sum of the distances between all unordered pairs of vertices of H, that is,

$$\begin{aligned} W(H) = \sum _{\{u,v\} \in \left( {\begin{array}{c}V(H) \\ 2\end{array}}\right) }d_H(u,v). \end{aligned}$$

The Cartesian product $H \,\square \,H'$ of hypergraphs H and $H'$ is a hypergraph with the vertex set $V(H) \times V(H')$ and the edge set

$$\begin{aligned} \left\{ \{u\} \times e':\ u \in V(H),\ e' \in E(H') \right\} \cup \left\{ e \times \{u'\}:\ e \in E(H),\ u' \in V(H')\right\} . \end{aligned}$$

Just as Cartesian products of graphs, Cartesian products of hypergraphs have several nice properties, cf [15, 16]. In particular, if H and $H'$ are k-uniform hypergraphs, then $H \,\square \,H'$ is also k-uniform, and the Cartesian product operation is associative. For $k \ge 2$, let ${{{\mathcal {Q}}}}_k$ denote the hypergraph with k vertices and a single edge containing all the vertices. For $n \ge 1$, the k-uniform n-cube ${{{\mathcal {Q}}}}_k^{n}$ is the Cartesian product of k copies of $\mathcal{Q}_k$. See Fig. 1 where ${{{\mathcal {Q}}}}_3^{1}$, ${{{\mathcal {Q}}}}_3^{2}$, and ${{{\mathcal {Q}}}}_3^{3}$ are presented.

Fig. 1

Cube-hypergraphs

The k-uniform n-cube ${{{\mathcal {Q}}}}_k^{n}$ can be equivalently described as follows. Its vertex set is $\{0,1, \ldots , k-1\}^n$ and an edge consists of all n-tuples which coincide on $n-1$ coordinates while the remaining coordinate ranges over $\{0, 1, \ldots , k-1\}$. It follows that $|V({{{\mathcal {Q}}}}_k^{n})| = k^n$ and $|E({{{\mathcal {Q}}}}_k^{n})| = n \cdot k^{n-1}$. Note that ${{{\mathcal {Q}}}}_2^{n}$ is a 2-uniform hypergraph which is as a graph known as the n-cube.

2.2 Partial cube-hypergraphs

A k-uniform hypergraph H is a partial cube-hypergraph if H is an isometric subhypergraph of some ${{{\mathcal {Q}}}}_k^{n}$.

A hypergraph H is edge-gated if for any edge $e = \{a_1, \ldots , a_k\} \in E(H)$ and any vertex $x\in V(H)$ there exists $j \in [k]$ such that $d_H(x, a_i) = d_H(x, a_j) + 1$ for $i \in [k]$, $i\ne j$. We also say that $a_j$ is the gate of x in e. Note that if $x \in e$ then x is its own gate in e.

It is easy to see that in 2-uniform hypergraphs (alias graphs) H is edge-gated if and only if H is bipartite. From this reason, edge-gated hypergraphs were named bipartite hypergraphs in [7], where this concept was originally introduced. However, since there are numerous ways how bipartite graphs can be extended to hypergraphs we decided to change the terminology. The present terminology also mimics the established graph terminology, cf. [10].

It is easy to see that if hypergraphs H and $H'$ are both edge-gated then so is $H \,\square \,H'$. Also, if $H'$ is a connected isometric subgraph of an edge-gated hypergraph H, then $H'$ is edge-gated as well. It follows that partial cube-hypergraphs and hence in particular k-uniform n-cubes are edge-gated.

If x and y are two (adjacent) vertices of a hypergraph H, then let H(x, y) denote the set of vertices that are closer to x than to y, that is,

$$\begin{aligned} H(x,y) = \{ z \in V(H):\ d_H(z, x) < d_H(z, y)\}. \end{aligned}$$

Further, if $e=\{a_1, \ldots , a_k\} \in E(H)$, then let

$$\begin{aligned} H(a_i,e) = \{ z \in V(H):\ d_H(z, a_i) < d_H(z, a_j),\ j\ne i \}. \end{aligned}$$

In addition, set

$$\begin{aligned} H_e = \{H(a_1,e), \ldots , H(a_k, e)\}. \end{aligned}$$

Let now H be an edge-gated hypergraph and $e=\{a_1, \ldots , a_k\} \in E(H)$. Since $a_i \in H(a_i, e)$ we have the following important facts.

Lemma 1.1

[7, Lemma 1(ii), Lemma 2] If H is an edge-gated hypergraph and $e = \{a_1, \ldots , a_k\} \in E(H)$, then the following statements hold.

• (i) $H_e$ is a partition of V(H).

• (ii) If $e' \in E(H)$, then either $|e' \cap H(a_i, e)| = 1$ for all $i \in [k]$ or $e' \subseteq H(a_i, e)$ for some $i \in [k]$.

We next recall the following, key definition from [7]. If H is a hypergraph, then the binary relation $\Theta$ is defined on E(H) as follows:

$$\begin{aligned} e \Theta e' \ \equiv \ \forall A \in H_e:\ e'\cap A \ne \emptyset . \end{aligned}$$

Note first that for any edge $e \in E(H)$ we have $e\Theta e$. If H is edge-gated, then $\Theta$ is also symmetric by Lemma 2.1(ii). Moreover, we recall the following important fact.

Lemma 1.2

[7, Lemma 3] If H is an edge-gated hypergraph and for every $e\in E(H)$, every $A \in H_e$ is convex, then $f \Theta f'$ if and only if $H_f = H_{f'}$.

For hypergraphs which fulfil the conditions of Lemma 2.2, the relation $\Theta$ is an equivalence relation where the transitivity is guaranteed by Lemma 2.2. Partial cube-hypergraphs which are k-uniform can now be characterized as follows.

Theorem 1.3

[7, Theorem 1] A k-uniform hypergraph H is a partial cube-hypergraph if and only if H is edge-gated and for every $e \in E(H)$, every $A \in H_e$ is convex.

Theorem 1.4

[7, Theorem 2] A k-uniform hypergraph H is a partial cube-hypergraph if and only if H is edge-gated and $\Theta$ is transitive.

3 Cut method for hypergraphs

We now have all the tools needed for the main theorem of this article. But before we can formulate it, we need two additional auxiliary results and the following concepts.

If H is a connected hypergraph, then $F \subseteq E(H)$ is a cut if the edges from F are pairwise disjoint and $H-F$ consists of at least two components. We further say that the cut F is a convex cut if the vertex set of each component of $H - F$ is a convex set.

Let H be a k-uniform partial cube-hypergraph. Theorems 2.3 and 2.4 imply that the $\Theta$ relation is an equivalence relation on E(H). We will denote its equivalence classes by $F_1, \ldots , F_m$. In addition, if $e \in E(H)$, then the equivalence class with the representative e will also be denoted by $F_e$, that is, $F_e= \{f \in E(H) \,\ e \Theta f \}$.

From Lemma 2.2 we infer that the hypergraph $H - F_e$ consists of components whose vertex sets are precisely the sets from $H_e$. This yields the following important fact.

Proposition 1.5

Let H be k-uniform partial cube-hypergraph and let $e \in E(H)$. Then $H - F_e$ has exactly k components.

We also need the following auxiliary result.

Proposition 1.6

Let H be k-uniform partial cube-hypergraph and let $e \in E(H)$. If u and v are vertices from different components of $H - F_e$, then every shortest u, v-path contains exactly one edge from $F_e$.

Proof

By Proposition 3.1, $H - F_e$ contains k components which we denote by $H_1, \ldots H_k$. We may without loss of generality assume that $u \in H_1$ and $v \in H_k$. Furthermore, let $F_e = \{e_1, \ldots , e_{\ell }\}$. By Lemma 2.2(ii) the vertices $u_i$ and $v_i$ defined as

$$\begin{aligned} \{u_i\} = V(H_1) \cap e_i \quad \text{ and } \quad \{v_i\} = V(H_k) \cap e_i \end{aligned}$$

are well-defined for every $i \in [\ell ]$. From the edge-gated property of H it follows that $d_H(u_i, v) = d_H(v_i, v) + 1$. Since every u, v-path contains at least one of the vertices $u_i$, every shortest u, v-path contains exactly one of the edges $e_i$, $i \in [\ell ]$. $\square$

Let H be a k-uniform partial cube-hypergraph and let $F_1, \ldots , F_m$ be its $\Theta$-classes. By Proposition 3.1, $H - F_i$ has k components, we denote them in the sequel by $H_1(F_i), \ldots , H_k(F_i)$. Set in addition

$$\begin{aligned} n_j(F_i) = |V(H_j(F_i))|, \ j \in [k], \ i \in [m]. \end{aligned}$$

(1)

The cut method for hypergraphs now reads as follows.

Theorem 1.7

If H is a k-uniform partial cube-hypergraph, $F_1, \ldots , F_m$ are its $\Theta$-classes, and integers $n_j(F_i)$ are defined as in (1), then

$$\begin{aligned} W(H) = \sum _{i=1}^m \sum _{ \{j, j'\} \in {[k] \atopwithdelims ()2}} n_j(F_i) \cdot n_{j'}(F_i) . \end{aligned}$$

Proof

Since $F_1, \ldots , F_m$ form a partition of E(H), the idea is to consider the contribution of each edge to W(H). Consider arbitrary vertices u and v of H and an arbitrary u, v-shortest path P. By Proposition 3.2, edges from P pairwise lie in different $\Theta$-classes of E(H). If e is an edge of P, then the contribution of $F_e$ to the distance $d_H(u,v)$ is exactly 1. Consequently, the contribution of $F_e$ to W(H) is exactly

$$\begin{aligned} \sum _{ \{j, j'\} \in {[k] \atopwithdelims ()2}} n_j(F_e) \cdot n_{j'}(F_e). \end{aligned}$$

Summing over all $\Theta$-classes the result follows. $\square$

4 Some applications

In this section we give some examples and applications of Theorem 3.3.

4.1 Cube-hypergraphs

Cube-hypergraphs are partial cube-hypergraphs by definition. Hence Theorem 3.3 applies to them and leads to the following result.

Proposition 1.8

If $n \ge 1$ and $k \ge 2$, then

$$\begin{aligned} W({{{\mathcal {Q}}}}_k^{n}) = n {k \atopwithdelims ()2} k^{2(n-1)}. \end{aligned}$$

Proof

To apply Theorem 3.3, we first determine the $\Theta$-classes of ${{{\mathcal {Q}}}}_k^{n}$. Let an edge $e \in E({{{\mathcal {Q}}}}_k^{n})$ be of the form $\{a_i = (i,0,\ldots ,0) \, \ i \in \{0,1, \ldots , k-1\}\}$. Then $H(e, a_i)$ contains the vertices $(i, v_2, \ldots , v_n)$, where $(v_2, \ldots , v_n) \in \{0,1,\ldots , k-1\}^{n-1}$. By Theorem 2.3, sets $H(e, a_i)$ are convex and the subhypergraphs induced by them are isomorphic to ${{{\mathcal {Q}}}}_k^{n-1}$. Then the $\Theta$-class $F_e = F_1$ contains all the edges whose last $n-1$ coordinates are fixed and the first coordinate ranges from 0 to $k-1$. Using the same reasoning we get that every $\Theta$-class is of the above form. Therefore ${{{\mathcal {Q}}}}_k^{n}$ has $\Theta$-classes $F_1, \ldots , F_n$ where ${{{\mathcal {Q}}}}_k^{n} - F_i$ has components which are isomorphic to ${{{\mathcal {Q}}}}_k^{n-1}$ for $i \in [n]$. It then follows that $n_j(F_i) = k^{n-1}$ for every $j \in [k]$ and $i \in [n]$. From Theorem 3.3 it follows that

$$\begin{aligned} W({{{\mathcal {Q}}}}_k^{n})&= \sum _{i=1}^n \sum _{ \{j, j'\} \in {[k] \atopwithdelims ()2}} k^{n-1}\cdot k^{n-1} = n \left( {\begin{array}{c}k\\ 2\end{array}}\right) k^{2(n-1)}, \end{aligned}$$

which we wanted to show. $\square$

Setting $k=2$, the hypergraph ${{{\mathcal {Q}}}}_2^{n}$ is the n-cube graph $Q_n$ and Proposition 4.1 implies a well-known result $W(Q_n) = n4^{n-1}$, which can in particular be deduced from the formula for the Wiener index of Cartesian products [13].

4.2 Hypertrees

A hypergraph T is a hypertree if it is connected, linear, and has no cycles. Here a cycle in a hypergraph is defined just as we defined a path except that the first and the last vertex from the corresponding sequence coincide. A hypertree which is linear and k-uniform is a partial cube-hypergraph where every edge e is it own $\Theta$-class. Hence Theorem 3.3 as a special case yields the following result.

Corollary 1.9

If T is a k-uniform hypertree, then

$$\begin{aligned} W(T) = \sum _{e \in E(T)} \sum _{\{j, j'\} \in \left( {\begin{array}{c}[k]\\ 2\end{array}}\right) } n_j(e) \cdot n_{j'}(e), \end{aligned}$$

where $n_j(e) = n_j(F_e)$.

Actually Corollary 4.2 holds also if we do not require that a hypertree is uniform. For this sake one just needs to reformulate Proposition 3.1 such that its conclusion asserts that for any edge $e \in E(T)$, the hypergraph $T - e$ has exactly |e| components. Moreover the second key auxiliary result, Proposition 3.2, also holds by the fact that in a hypertree there is a unique shortest path between two vertices. In this way Corollary 4.2 extends to

Theorem 1.10

[28, Theorem 3] If T is a hypertree, then

$$\begin{aligned} W(T) = \sum _{e \in E(T)} \sum _{\{j, j'\} \in \left( {\begin{array}{c}[|e|]\\ 2\end{array}}\right) } n_j(e) \cdot n_{j'}(e). \end{aligned}$$

For an example consider a hypertree $T_1$ from Fig. 2. The hypertree $T_1$ has seven vertices and four edges. We now apply Theorem 4.3. For instance consider the edge $e = \{a_1,a_2,a_3\}$ as shown in the figure. Then $n_1(e) = 2$, $n_2(e) = 1$ and $n_3(e) = 4$. Therefore the contribution of e to the formula of Theorem 4.3 is $2\cdot 1 + 1\cdot 4 + 2\cdot 4$. Doing similar computations for the other three edges (see the bottom line of Fig. 2) we get

$$\begin{aligned} W(T_1) = 1\cdot 6 + (2\cdot 1 + 1\cdot 4 + 2\cdot 4) + (5 \cdot 1 + 5 \cdot 1+ 1 \cdot 1) + 6 \cdot 1 =37. \end{aligned}$$

Fig. 2

Hypertree $T_1$

A limitation of Theorem 4.3 is that it only works for linear hypertrees. On the other hand, there exist many different definitions of acyclicity in hypergraphs, where some of them also allow for non-linear hypergraphs. See for example [17]. We next show with an example that the main idea of Theorem 4.3 can sometimes be generalized to such cases as well.

Define the linear phenylene hypergraphs $LP_n$, $n \ge 2$, as follows. (For some recent studies of phenylenes in mathematical chemistry see [9, 20, 23, 27].) $LP_n$ has vertex set [6n]. It has $2n - 1$ hyperedges. The first n of them are of the form $\{6i + 1, 6i + 2, \ldots , 6i + 6\}$ where $i \in \{0,1, \ldots , n-1\}$, and the remaining $n-1$ hyperedges edges are of the form $\{6i + 5, 6i + 6, 6i + 7, 6i + 8\}$, where $i \in \{0,1,\ldots , n-2\}$. In Fig. 3 the hypergraph $LP_4$ is drawn.

Fig. 3

Hypergraph $LP_4$

It is easy to see that every edge $e \in E(LP_n)$ is a convex cut with the following property. Taking any two vertices u, v from different components of $LP_n - e$, every shortest u, v-path contains e (exactly once). Note, however, that the two vertices which lie in the intersection of two hyperedges are not separated by any of the cuts. But it is clear that the distance between such two vertices is 1. Together there are $2(n-1)$ such pairs and therefore this number needs to be added to the Wiener index of $LP_n$. This is enough to calculate the Wiener index of $LP_n$ using cut method as follows.

Removing an edge of the form $\{6i + 1, 6i + 2, \ldots , 6i + 6\}$, where $i \in [n-2]$, produces four components where two of them contain a single vertex and the remaining two have $6i + 2$ and $6(n-i-1) + 2$ vertices, respectively. The cases when $i=0$ or $i = n-1$ give five components each, four of them contain a single vertex, while the remaining one contains $6n - 4$ vertices. On the other hand, removing an edge of the form $\{6i + 5, 6i + 6, 6i + 7, 6i + 8\}$ produces two components with $6(i+1)$ and $6(n-i-1)$ vertices, respectively. Therefore, the contribution of all these cuts to the Wiener index of $LP_n$ for $n>1$ is

$$\begin{aligned}&\sum _{i=1}^{n-2} \left[ 2(6i + 2 + 6(n - i - 1) + 2) + (6i+2)(6n-6i-4) +1 \right] \\&\quad + 2 \left( \left( {\begin{array}{c}4\\ 2\end{array}}\right) + 4 (6n - 4) \right) \\&\quad +\sum _{i=0}^{n-2}\left[ 6(i+1)\cdot 6(n-i-1)\right] = 12n^3 + 6n^2 - 5n + 2, \end{aligned}$$

where the second line above comes from the contribution of the first hyperedge and the last hyperedge containing six vertices. Adding to this expression the contribution $2(n-1)$ from previous paragraph and performing a straightforward computation we arrive to the following result.

Proposition 1.11

If $n \ge 2$ then, $W(LP_n) = 12n^3 + 6n^2 - 3n$.

4.3 More elaborate example

The cut method as developed in Sect. 3 assumes that a hypergraph is a k-uniform partial cube-hypergraph. In general this is a strong assumption. We have just demonstrated in Sect. 4.2 that the method can be extended also when the hypergraph is not k-uniform partial cube-hypergraph, provided that Propositions 3.1 and 3.2 remain valid. In the subsequent example we further elaborate this idea on a mulecular hypergraph H of a Clar structure which is shown in Fig. 4a and in [14, Fig. 3].

Fig. 4

Hypergraph H and its convex cuts

There are two different types of cuts in H. The cut of type I consists of the central 6-edge and three 2-edges that do not intersect it as can be seen in Fig. 4b. A cut of type II consists of a non-central 6-edge and its opposite 2-edge as can be seen in Fig. 4c. Both cuts are convex and also the conclusion of Proposition 3.2 holds. This, together with the fact that E(H) partitions into one cut of type I and six cuts of type II, allows us to use the cut method to calculate Wiener index of H as

$$\begin{aligned} W(H) = \left( {\begin{array}{c}6\\ 2\end{array}}\right) 7\cdot 7 + 6\left( \left( {\begin{array}{c}4\\ 2\end{array}}\right) +4\cdot 7 + 4\cdot 31 + 7\cdot 31 \right) =2985. \end{aligned}$$