Electronic Journal of Graph Theory and Applications

Ali Sadeghieh^a, Nima Ghanbari^b, Saeid Alikhani^b

sadeghieh@iauyazd.ac.ir, n.ghanbari.math@gmail.com, alikhani@yazd.ac.ir

Let G be a finite connected graph of order n. The Gutman index Gut(G) of G is defined as \(\sum_{\{x,y\}\subseteq V(G)}deg(x)deg(y)d(x,y)\), where deg(x) is the degree of vertex x in G and d(x,y) is the distance between vertices x and y in G. A cactus graph is a connected graph in which no edge lies in more than one cycle. In this paper we compute the exact value of Gutman index of some cactus chains.

Keywords: Gutman index, distance, graph Mathematics Subject Classification: 05C12

DOI: 10.5614/ejgta.2018.6.1.10

1. Introduction

Let G=(V,E) be a finite, connected, simple graph. We denote the degree of a vertex v in G by deg(v), and for two vertices u,v in G, d(u,v) denotes the usual distance between u and v in G, i.e., the minimum number of edges on a path from u to v. A topological index of G is a real number related to G. It does not depend on the labeling or pictorial representation of a graph. The Wiener index W(G) is the first distance based topological index defined as \(W(G) = \sum_{\{u,v\}\subseteq G} d(u,v) = \frac{1}{2} \sum_{u,v\in V(G)} d(u,v)\) with the summation runs over all pairs of vertices of G [12]. The topological indices and graph invariants based on distances between vertices of a graph are widely used for characterizing molecular graphs, establishing relationships between structure and properties of molecules, predicting biological activity of chemical compounds, and making

Received: 27 May 2016, Revised: 9 January 2018, Accepted: 20 February 2018.

^&lt;sup>a</sup>Department of Mathematics, Yazd branch, Islamic Azad University, Yazd, Iran

^&lt;sup>b</sup>Department of Mathematics, Yazd University, 89195-741, Yazd, Iran

their chemical applications. The Wiener index is one of the most used topological indices with high correlation with many physical and chemical indices of molecular compounds [12]. The degree distance of G, denoted by DD(G), is defined as \(DD(G) = \frac{1}{2} \sum_{u,v \in V(G)} d(u,v)[d(u) +\)d(v) with the summation runs over all pairs of vertices of G. In [4] Gutman showed that if T is a tree of order n, then DD(T) = 4W(G) - n(n-1). The Gutman index Gut(G) of G is defined as \(Gut(G) = \sum_{\{x,y\}\subseteq V(G)} deg(x) deg(y) d(x,y)\) ([4]). The Gutman index, a Schultz-type molecular topological index and a variant of the well known and much studied Wiener Index, was introduced in 1994 by Gutman [4] as a kind of a vertex-valency-weighted sum of the distances between all pairs of vertices in a graph. Gutman revealed that in the case of acyclic structures, the index is closely related to the Wiener Index and reects precisely the same structural features of a molecular as the Wiener Index does. A question, on whether theoretical investigations on the Gutman index focusing on the more difficult case of polycyclic molecules can be done, was posed ([8]). Mukwembi in [8] proved that \(Gut(G) \leq \frac{2^4}{5^5}n^5 + O(n^4)\), where n is the order of G. V. Sheeba Agnes in [11] determined the degree distance and the Gutman index of the corona product of two graphs. Also he obtained, the exact degree distance and Gutman index of certain classes of graphs. The exact value of the Gutman indices of the Cartesian product, the wreath product of graphs, and as results the exact value of Gutman indices of the hypercube, torus, grid, Hamming graph and the fence graph are given in [9].

In this paper we consider a class of simple linear polymers called cactus chains. Cactus graphs were first known as Husimi tree, they appeared in the scientific literature some sixty years ago in papers by Husimi and Riddell concerned with cluster integrals in the theory of condensation in statistical mechanics [5, 6, 10]. We refer the reader to papers [2, 7] for some aspects of parameters of cactus graphs. A cactus graph is a connected graph in which no edge lies in more than one cycle. Consequently, each block of a cactus graph is either an edge or a cycle. If all blocks of a cactus G are cycles of the same size i, the cactus is i-uniform. A triangular cactus is a graph whose blocks are triangles, i.e., a 3-uniform cactus. A vertex shared by two or more triangles is called a cut-vertex. If each triangle of a triangular cactus G has at most two cut-vertices, and each cut-vertex is shared by exactly two triangles, we say that G is a chain triangular cactus. By replacing triangles in this definitions with cycles of length 4 we obtain cacti whose every block is \(C_4\). We call such cacti square cacti. Note that the internal squares may differ in the way they connect to their neighbors. If their cut-vertices are adjacent, we say that such a square is an ortho-square; if the cut-vertices are not adjacent, we call the square a para-square[1].

In the next section, we compute the Gutman index of triangular and square cactus chains. In Section 3, we compute Gutman index of two kind of chain hexagonal cactus.

2. Gutman index of triangular and square cactus chains

First we consider a chain triangular. An example of a chain triangular cactus is shown in Figure 1. We call the number of triangles in G, the length of the chain. Obviously, all chain triangular cacti of the same length are isomorphic. Hence, we denote the chain triangular cactus of length n by \(T_n\). Here we compute the exact value of Gutman index of \(T_n\).

Computation of Gutman index of some cactus chains | A. Sadeghieh et al.

Figure 1. Chain triangular graph \(T_n\).

Theorem 2.1. The Gutman index of the chain triangular cactus \(T_n\) \((n \ge 2)\) is

\[Gut(T_n) = 6n^2(n+1).\]

Proof. Let u and v be two arbitrary vertices of \(T_n\). Suppose that d(u,v)=k. We have the following cases:

• (1) If d(u, v) = 1 then there are two pairs of vertices such as \(u, v \in V(G)\) with d(u) = d(v) = 2, and 2n pairs of vertices \(u, v \in V(G)\) with d(u) = 2 and d(v) = 4, and there are n 2 pairs of vertices such as \(u, v \in V(G)\) with d(u) = d(v) = 4.
• (2) If d(u,v)=k and \(2 \le k \le n-1\) then there are n-k+3 pairs of vertices such as \(u,v \in V(G)\) with d(u)=d(v)=2, there are 2(n-k+1) pairs of vertices \(u,v \in V(G)\) with d(u)=2 and d(v)=4, and n-k-1 pairs of vertices \(u,v \in V(G)\) with d(u)=d(v)=4.
• (3) If d(u, v) = n then there are four pairs of vertices \(u, v \in V(G)\) with d(u) = d(v) = 2.

So by definition of Gutman index, we have:

\[Gut(T_n) = \sum_{\{u,v\} \subseteq V(G)} d(u,v)d(u)d(v)\] \[= \sum_{\{u,v\} \subseteq V(G),d(u,v)=k,k \in \{2,\dots,n-1\}} d(u,v)d(u)d(v)\] \[+ \sum_{\{u,v\} \subseteq V(G),d(u,v)=1} d(u,v)d(u)d(v)\] \[+ \sum_{\{u,v\} \subseteq V(G),d(u,v)=n} d(u,v)d(u)d(v)\] \[= \sum_{k=2}^{n-1} 4k(n-k+3) + \sum_{k=2}^{n-1} 16k(n-k+1) + \sum_{k=2}^{n-1} 16k(n-k-1)\] \[+2(4) + 2n(8) + (n-2)(16) + 4(2)(2)n\] \[= 48n - 24 + (36\sum_{k=2}^{n-1} k(n-k-1)) + 48\sum_{k=2}^{n-1} k\]

Computation of Gutman index of some cactus chains | A. Sadeghieh et al.

Figure 2. Para-chain square cactus graph \(Q_n\).

\[= 48(\frac{n(n-1)}{2} - 1) + 48n - 24 + 36\sum_{k=2}^{n-1} k(n-k-1)\] \[= 24n^2 + 24n - 72 + 36\sum_{k=2}^{n-1} k(n-k-1)\] \[= 24n^2 + 24n - 72 + 6n^3 - 18n^2 - 24n + 72\] \[= 6n^2(n+1). \quad \Box\]

By replacing triangles in the definitions of triangular cactus \(T_n\), with cycles of length 4 we obtain cacti whose every block is \(C_4\). We call such cacti, square cacti. An example of a square cactus chain is shown in Figure 2. We see that the internal squares may differ in the way they connect to their neighbors. If their cut-vertices are adjacent, we say that such a square is an ortho-square; if the cut-vertices are not adjacent, we call the square a para-square. We consider a para-chain of length n, which is denoted by \(Q_n\) as shown in Figure 2. The following theorem gives the exact value of Gutman index of \(Q_n\).

Theorem 2.2. The Gutman index of the Para-chain square cactus graph \(Q_n\) \((n \ge 2)\) is

\[Gut(Q_n) = \frac{32}{3}n(2n^2 + 1).\]

Proof. Suppose that u and v are two arbitrary vertices of \(Q_n\) and let d(u,v)=k. We have the following cases:

• (1) If d(u, v) = k and k = 2s + 1 (\(0 \le s \le n 2\)) then we have the following pairs of vertices:
  • (i) There are four pairs of vertices such as \(u, v \in V(G)\) with d(u) = d(v) = 2.
  • (ii) There are 4(n-s-1) pairs of vertices such as \(u,v\in V(G)\) with d(u)=2 and d(v)=4.
• (2) If d(u, v) = 2 then we have the following pairs of vertices:
  • (i) There are 5(n-1)+1 pairs of vertices such as \(u,v\in V(G)\) with d(u)=d(v)=2.
  • (ii) There are two pairs of vertices such as \(u, v \in V(G)\) with d(u) = 2 and d(v) = 4.
  • (iii) There are n-2 pairs of vertices such as \(u, v \in V(G)\) with d(u) = d(v) = 4.
• (3) If d(u, v) = k and k = 2s (\(2 \le s \le n 1\)) then we have the following pairs of vertices:

• (i) There are 4(n-s) pairs of vertices such as \(u, v \in V(G)\) with d(u) = d(v) = 2.
• (ii) There are two pairs of vertices such as \(u, v \in V(G)\) with d(u) = 2 and d(v) = 4.
• (iii) There are n-s-1 pairs of vertices such as \(u,v \in V(G)\) with d(u)=d(v)=4.
• (4) If d(u,v) = 2n-1, then there are four pairs of vertices such as \(u,v \in V(G)\) with d(u) = d(v) = 2.
• (5) If d(u, v) = 2n, then there is one pair of vertices such as \(u, v \in V(G)\) with d(u) = d(v) = 2.

So by definition of Gutman index we have:

\[Gut(Q_n) = \sum_{\{u,v\}\subseteq V(G)} d(u,v)d(u)d(v)\] \[= \sum_{\{u,v\}\subseteq V(G),d(u,v)=2s+1,s\in\{0,\dots,n-2\}} d(u,v)d(u)d(v)\] \[+ \sum_{\{u,v\}\subseteq V(G),d(u,v)=2} d(u,v)d(u)d(v)\] \[+ \sum_{\{u,v\}\subseteq V(G),d(u,v)=2s,s\in\{2,\dots,n-1\}} d(u,v)d(u)d(v)\] \[+ \sum_{\{u,v\}\subseteq V(G),d(u,v)=2n-1} d(u,v)d(u)d(v)\] \[+ \sum_{\{u,v\}\subseteq V(G),d(u,v)=2n-1} d(u,v)d(u)d(v)\] \[= \sum_{s=0}^{n-2} 4(2s+1)(2)(2) + \sum_{s=0}^{n-2} 4(n-s-1)(2s+1)(2)(4)\] \[+ (5(n-1)+1)(2)(2)(2) + 2(2)(2)(4) + (n-2)(2)(4)(4)\] \[+ \sum_{s=2}^{n-1} 4(n-s)(2s)(2)(2) + \sum_{s=2}^{n-1} 2(2s)(2)(4) + \sum_{s=2}^{n-1} (n-s-1)(2s)(4)(4)\] \[+ 4(2n-1)(2)(2) + 2n(2)(2)\] \[= \frac{32}{3}n(2n^2+1). \quad \Box\]

Now we consider another kind of square cactus chain and compute its Gutman index (Figure 3).

Theorem 2.3. The Gutman index of the Ortho-chain square cactus graph \(O_n\) \((n \ge 5)\) is

\[Gut(O_n) = \frac{32}{3}n^3 + 24n^2 - \frac{8}{3}n + 48.\]

Proof. Suppose that u and v are two vertices of \(O_n\) and let d(u,v)=k. We have the following cases:

Figure 3. Ortho-chain square cactus graph \(O_n\).

• (1) If d(u, v) = 1, then we have the following pairs of vertices:
  • (i) There are n+2 of vertices such as \(u,v \in V(G)\) with d(u)=d(v)=2.
  • (ii) There are 2n pairs of vertices such as \(u, v \in V(G)\) with d(u) = 2 and d(v) = 4.
  • (iii) There are n-2 pairs of vertices such as \(u, v \in V(G)\) with d(u) = d(v) = 4.
• (2) If d(u, v) = 2, then we have the following pairs of vertices:
  • (i) There are n+3 pairs of vertices such as \(u, v \in V(G)\) with d(u) = d(v) = 2.
  • (ii) There are 4(n-1) pairs of vertices such as \(u, v \in V(G)\) with d(u) = 2 and d(v) = 4.
  • (iii) There are n-3 pairs of vertices such as \(u, v \in V(G)\) with d(u) = d(v) = 4.
• (3) If d(u, v) = 3 then we have the following pairs of vertices:
  • (i) There are 3n pairs of vertices such as \(u, v \in V(G)\) with d(u) = d(v) = 2.
  • (ii) There are 4(n-3)+2 pairs of vertices such as \(u,v\in V(G)\) with d(u)=2 and d(v)=4.
  • (iii) There are n-4 pairs of vertices such as \(u,v \in V(G)\) with d(u)=d(v)=4.
• (4) If d(u,v) = k (\(4 \le k \le n-1\)) then we have the following pairs of vertices:
  • (i) There are 4(n-k+3) pairs of vertices such as \(u, v \in V(G)\) with d(u) = d(v) = 2.
  • (ii) There are 4(n-k)+2 pairs of vertices such as \(u,v\in V(G)\) with d(u)=2 and d(v)=4.
  • (iii) There are n-k-1 pairs of vertices such as \(u,v \in V(G)\) with d(u)=d(v)=4.
• (5) If d(u, v) = n then we have the following pairs of vertices:
  • (i) There are thirteen pairs of vertices such as \(u, v \in V(G)\) with d(u) = d(v) = 2.
  • (ii) There are two pairs of vertices such as \(u, v \in V(G)\) with d(u) = 2 and d(v) = 4.
• (6) If d(u,v) = n+1 then there are six pairs of vertices such as \(u,v \in V(G)\) with d(u) = d(v) = 2.
• (7) If d(u, v) = n + 2 then there is one pair of vertices such as \(u, v \in V(G)\) with d(u) = d(v) = 2.

So we have:

\[\begin{split} Gut(O_n) &= \sum_{\{u,v\} \subseteq V(G), d(u,v) = 1} d(u,v) d(u) d(v) + \sum_{\{u,v\} \subseteq V(G), d(u,v) = 2} d(u,v) d(u) d(v) \\ &= \sum_{\{u,v\} \subseteq V(G), d(u,v) = 3} d(u,v) d(u) d(v) \\ &+ \sum_{\{u,v\} \subseteq V(G), d(u,v) = k, k \in \{4,\dots,n-1\}} d(u,v) d(u) d(v) \\ &+ \sum_{\{u,v\} \subseteq V(G), d(u,v) = n} d(u,v) d(u) d(v) \\ &+ \sum_{\{u,v\} \subseteq V(G), d(u,v) = n+1} d(u,v) d(u) d(v) + \sum_{\{u,v\} \subseteq V(G), d(u,v) = n+2} d(u,v) d(u) d(v) \\ &= (n+2)(2)(2) + 2n(2)(4) + (n-2)(4)(4) \\ &+ (n+3)(2)(2)(2) + 4(n-1)(2)(2)(4) + (n-3)(2)(4)(4) \\ &+ 3n(3)(2)(2) + (4(n-3)+2)(3)(2)(4) + (n-4)(3)(4)(4) \\ &+ \sum_{k=4}^{n-1} 4(n-k+3)(k)(2)(2) + \sum_{k=4}^{n-1} (4(n-k)+2)(k)(2)(4) \\ &+ \sum_{k=4}^{n-1} (n-k-1)(k)(4)(4) \\ &+ 13n(2)(2) + 2n(2)(4) + 6(n+1)(2)(2) + (n+2)(2)(2) \\ &= 8n^3 + 32n^2 + 88n - 272 + \frac{8}{3}(n-4)(n-5)(n+6). \\ &= \frac{32}{3}n^3 + 24n^2 - \frac{8}{3}n + 48. \quad \Box \end{split}\]

3. Gutman index of chain hexagonal cactus

In this section we shall compute the exact value of Gutman index of some hexagonal cactus chains. Replacing triangles in the definitions of triangular cactus, by cycles of length 6 we obtain cacti whose every block is C6. We call such cacti, hexagonal cacti. An example of a hexagonal cactus chain is shown in Figure 4. We see that the internal hexagonal may differ in the way they connect to their neighbors. If their cut-vertices are adjacent, we say that such a square is an orthohexagonal; if the cut-vertices are not adjacent, we call the square a para-hexagonal. We consider a para-chain of length n, which is denoted by Lⁿ as shown in Figure 4. The following theorem gives the exact value of Gutman index of Ln. In this section we shall compute the Gutman index of two kinds of para-chain hexagonal cactus. The following theorem gives the Gutman index of Ln.

Theorem 3.1. The Gutman index of the Para-chain hexagonal cactus graph Lⁿ (n ≥ 3) is

\[Gut(L_n) = 36n(2n^2 + 1).\]

Figure 4. Para-chain hexagonal cactus graph \(L_n\).

Proof. Suppose that u and v are two vertices of \(L_n\) and let d(u,v)=k. We have the following cases:

• (1) If d(u, v) = 1, then we have the following pairs of vertices:
  • (i) There are 2n + 4 of vertices such as \(u, v \in V(G)\) with d(u) = d(v) = 2.
  • (ii) There are 4(n-1) pairs of vertices such as \(u, v \in V(G)\) with d(u) = 2 and d(v) = 4.
• (2) If d(u, v) = 2, then we have the following pairs of vertices:
  • (i) There are 6n pairs of vertices such as \(u, v \in V(G)\) with d(u) = d(v) = 2.
  • (ii) There are 4(n-1) pairs of vertices such as \(u, v \in V(G)\) with d(u) = 2 and d(v) = 4.
• (3) If d(u, v) = 3 then we have the following pairs of vertices:
  • (i) There are 10(n-1)+2 pairs of vertices such as \(u,v\in V(G)\) with d(u)=d(v)=2.
  • (ii) There are two pairs of vertices such as \(u, v \in V(G)\) with d(u) = 2 and d(v) = 4.
  • (iii) There are n-2 pairs of vertices such as \(u, v \in V(G)\) with d(u) = d(v) = 4.
• (4) If d(u, v) = k and k = 3s + 1 (\(1 \le s \le n 2\)) then we have the following pairs of vertices:
  • (i) There are 4(n-s+1) pairs of vertices such as \(u, v \in V(G)\) with d(u) = d(v) = 2.
  • (ii) There are 4(n-s-1) pairs of vertices such as \(u,v\in V(G)\) with d(u)=2 and d(v)=4.
• (5) If d(u, v) = k and k = 3s + 2 (\(1 \le s \le n 2\)) then we have the following pairs of vertices:
  • (i) There are 4(n-s) pairs of vertices such as \(u, v \in V(G)\) with d(u) = d(v) = 2.
  • (ii) There are 4(n-s-1) pairs of vertices such as \(u,v\in V(G)\) with d(u)=2 and d(v)=4.
• (6) If d(u, v) = k and k = 3s (\(2 \le s \le n 1\)) then we have the following pairs of vertices:
  • (i) There are 8(n-s) pairs of vertices such as \(u, v \in V(G)\) with d(u) = d(v) = 2.
  • (ii) There are two pairs of vertices such as \(u, v \in V(G)\) with d(u) = 2 and d(v) = 4.
  • (iii) There are n-s-1 pairs of vertices such as \(u,v \in V(G)\) with d(u)=d(v)=4.
  • (7) If d(u,v) = 3n-2 then there are eight pairs of vertices such as \(u,v \in V(G)\) with d(u) = d(v) = 2.
  • (8) If d(u,v) = 3n-1 then there are four pairs of vertices such as \(u,v \in V(G)\) with d(u) = d(v) = 2.
  • (9) If d(u,v) = 3n then there is one pair of vertices such as \(u,v \in V(G)\) with d(u) = d(v) = 2.

www.ejgta.org

Figure 5. Meta-chain graph Mn.

So by definition Gutman index we have:

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

146

Theorem 3.2. The Gutman index of the Para-chain hexagonal cactus graph \(M_n\) (\(n \ge 4\)) is \(Gut(M_n) = 48n^3 + 72n^2 - 28n + 16\).

Proof. Let d(u, v) = k. We have the following cases:

• (1) If d(u, v) = 1 then we have the following pairs of vertices:
  • (i) There are 2n + 4 of vertices such as \(u, v \in V(G)\) with d(u) = d(v) = 2.
  • (ii) There are 4(n-1) pairs of vertices such as \(u, v \in V(G)\) with d(u) = 2 and d(v) = 4.
• (2) If d(u, v) = 2 then we have the following pairs of vertices:
  • (i) There are 5n pairs of vertices such as \(u, v \in V(G)\) with d(u) = d(v) = 2.
  • (ii) There are 2n pairs of vertices such as \(u, v \in V(G)\) with d(u) = 2 and d(v) = 4.
  • (iii) There are n-2 pairs of vertices such as \(u, v \in V(G)\) with d(u) = d(v) = 4.
• (3) If d(u, v) = 3 then we have the following pairs of vertices:
  • (i) There are 5n + 2 pairs of vertices such as \(u, v \in V(G)\) with d(u) = d(v) = 2.
  • (ii) There are 6n-10 pairs of vertices such as \(u, v \in V(G)\) with d(u)=2 and d(v)=4.
• (4) If d(u, v) = 4 then we have the following pairs of vertices:
  • (i) There are 9(n-1)-2 pairs of vertices such as \(u,v \in V(G)\) with d(u)=d(v)=2.
  • (ii) There are 2(n-1) pairs of vertices such as \(u, v \in V(G)\) with d(u) = 2 and d(v) = 4.
  • (iii) There are n-3 pairs of vertices such as \(u,v \in V(G)\) with d(u)=d(v)=4.
• (5) If d(u, v) = k and k = 2s + 1 (\(2 \le s \le n 2\)) then we have the following pairs of vertices:
  • (i) There are 6(n-s+1)+2 pairs of vertices such as \(u,v \in V(G)\) with d(u)=d(v)=2.
  • (ii) There are 6(n-s-1)+2 pairs of vertices such as \(u,v\in V(G)\) with d(u)=2 and d(v)=4.
• (6) If d(u, v) = k and k = 2s (\(3 \le s \le n 1\)) then we have the following pairs of vertices:
  • (i) There are 10(n-s+1)-1 pairs of vertices such as \(u, v \in V(G)\) with d(u)=d(v)=2.
  • (ii) There are 2(n-s+1) pairs of vertices such as \(u,v\in V(G)\) with d(u)=2 and d(v)=4.
  • (iii) n-s-1 pairs of vertices such as \(u,v \in V(G)\) with d(u)=d(v)=4.
• (7) If d(u, v) = 2n 1 then we have the following pairs of vertices:
  • (i) There are fourteen pairs of vertices such as \(u, v \in V(G)\) with d(u) = d(v) = 2.
  • (ii) There are two pairs of vertices such as \(u, v \in V(G)\) with d(u) = 2 and d(v) = 4.
• (8) If d(u, v) = 2n then there are ten pairs of vertices such as \(u, v \in V(G)\) with d(u) = d(v) = 2.
• (9) If d(u, v) = 2n + 1 then there are four pairs of vertices such as \(u, v \in V(G)\) with d(u) = d(v) = 2.
• (10) If d(u,v) = 2n + 2 then there is one pair of vertices such as \(u,v \in V(G)\) with d(u) = d(v) = 2.

So we have:

\[Gut(M_n) = \sum_{\{u,v\} \subseteq V(G), d(u,v) = 1} d(u,v)d(u)d(v) + \sum_{\{u,v\} \subseteq V(G), d(u,v) = 2} d(u,v)d(u)d(v)\] \[= \sum_{\{u,v\} \subseteq V(G), d(u,v) = 3} d(u,v)d(u)d(v) + \sum_{\{u,v\} \subseteq V(G), d(u,v) = 4} d(u,v)d(u)d(v)\] \[+ \sum_{\{u,v\} \subseteq V(G), d(u,v) = 2s, s \in \{2, \dots, n-2\}} d(u,v)d(u)d(v)\] \[+ \sum_{\{u,v\} \subseteq V(G), d(u,v) = 2s+1, s \in \{3, \dots, n-1\}} d(u,v)d(u)d(v)\] \[+ \sum_{\{u,v\} \subseteq V(G), d(u,v) = 2n-1} d(u,v)d(u)d(v) + \sum_{\{u,v\} \subseteq V(G), d(u,v) = 2n} d(u,v)d(u)d(v)\] \[+ \sum_{\{u,v\} \subseteq V(G), d(u,v) = 2n+1} d(u,v)d(u)d(v) + \sum_{\{u,v\} \subseteq V(G), d(u,v) = 2n+2} d(u,v)d(u)d(v)\] \[+ \sum_{\{u,v\} \subseteq V(G), d(u,v) = 2n+1} d(u,v)d(u)d(v) + \sum_{\{u,v\} \subseteq V(G), d(u,v) = 2n+2} d(u,v)d(u)d(v)\] \[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\] \[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\] \[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\] \[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\] \[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\] \[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\] \[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\] \[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\] \[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\] \[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\] \[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\] \[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\] \[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\] \[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

Let G be a connected graph constructed from pairwise disjoint connected graphs G1, ..., G^k as follows. Select a vertex of G1, a vertex of G2, and identify these two vertices. Then continue in this manner inductively. Note that the graph G constructed in this way has a tree-like structure, the Gi's being its building stones. Usually say that G is obtained by point-attaching from G1, ..., G^k and that Gi's are the primary subgraphs of G. A particular case of this construction is the decomposition of a connected graph into blocks (see [3]). Cactus chains which we considered in this paper are particular cases of point attaching of cycles of length three, four and six. As another example consider the graph Q(m, n) constructed in the following manner: consider the graph K^m and m copies of Kn. The graph Q(m, n) is obtained by identifying each vertex of K^m with a vertex of a unique Kⁿ (see Figure 6). We end this paper by computing the Gutman index of the graph Q(m, n).

Figure 6. The graph Q(m, n).

Theorem 3.3. The Gutman index of the graph Q(m, n) (m, n > 2) is

\[\frac{1}{2}m(4m^2n^2+4mn^3+n^4+m^3-6m^2n-14mn^2-7n^3-m^2+12mn+13n^2+m-7n-1).\]

Proof. Suppose that u and v are two vertices of Q(m,n) and let d(u,v)=k. We have the following cases:

• (1) If d(u,v)=1, then there are \(\frac{m(n-1)(n-2)}{2}\) of vertices \(u,v\in V(G)\) with d(u)=d(v)=n-1, m(n-1) pairs of vertices such as \(u,v\in V(G)\) with d(u)=n-1, d(v)=m+n-2, and there are \(\frac{m(m-1)}{2}\) pairs of vertices such as \(u,v\in V(G)\) with d(u)=d(v)=m+n-2.
• (2) If d(u, v) = 2, then there are m(m-1)(n-1) pairs of vertices \(u, v \in V(G)\) with d(u) = n-1 and d(v) = m + n 2.
• (3) If d(u,v)=3, then there are \(\frac{m(n-1)^2(m-1)}{2}\) pairs of vertices \(u,v\in V(G)\) with d(u)=d(v)=n-1.

So we have:

\[Gut(O(m,n)) = \sum_{\{u,v\} \subseteq V(G), d(u,v) = 1} d(u,v)d(u)d(v) + \sum_{\{u,v\} \subseteq V(G), d(u,v) = 2} d(u,v)d(u)d(v)\] \[= \sum_{\{u,v\} \subseteq V(G), d(u,v) = 3} d(u,v)d(u)d(v)\] \[= \frac{m(n-1)(n-2)}{2}(n-1)(n-1) + m(n-1)(n-1)(m+n-2)\] \[+ \frac{m(m-1)}{2}(m+n-2)^{2}\] \[+2m(m-1)(n-1)(n-1)(m+n-2)\]

\[+3\frac{m(m-1)}{2}(n-1)^{2}\] \[= \frac{1}{2}m(4m^{2}n^{2} + 4mn^{3} + n^{4} + m^{3} - 6m^{2}n\] \[-14mn^{2} - 7n^{3} - m^{2} + 12mn + 13n^{2} + m - 7n - 1). \quad \Box\]

Acknowledgements

The authors would like to express their gratitude to the referee for helpful comments. The first author would like to thank Islamic Azad University, Yazd Branch for support.

References

• [1] S. Alikhani, S. Jahari, M. Mehryar and R. Hasni, Counting the number of dominating sets of cactus chains, Opt. Adv. Mat. Rapid Comm. 8 (9-10) (2014), 955–960.
• [2] M. Chellali, Bounds on the 2-domination number in cactus graphs, Opuscula Math. 2 (2006), 5–12.
• [3] E. Deutsch and S. Klavzar, Computing the Hosoya polynomial of graphs from primary sub- ˇ graphs, MATCH Commun. Math. Comput. Chem. 70 (2013), 627–644.
• [4] I. Gutman, Selected Properties of the Schultz Molecular Topological Index, J. Chem. Inf. Comput. Sci. 34 (1994), 1087–1089.
• [5] F. Harary and B. Uhlenbeck, On the number of Husimi trees, I, Proc. Nat. Acad. Sci. 39 (1953), 315–322.
• [6] K. Husimi, Note on Mayer's theory of cluster integrals, J. Chem. Phys. 18 (1950), 682–684.
• [7] S. Majstorovic, T. Do ´ sli ˇ c and A. Klobu ´ car, ˇ k-domination on hexagonal cactus chains, Kragujevac J. Math. 36 (2) (2012), 335–347.
• [8] S. Mukwembi, On the upper bound of Gutman index of graphs, MATCH Commun. Math. Comput. Chem. 68 (2012), 343–348.
• [9] P. Paulraja and V. Sheeba Agnes, Gutman index of product graphs, Discrete Math. Alg. Appl. 6 (4) (2014), 1450058.
• [10] R.J. Riddell, Contributions to the theory of condensation, Ph.D. Thesis, Univ. of Michigan, Ann Arbor, 1951.

• [11] V. Sheeba Agnes, Degree distance and Gutman index of corona product of graphs, Trans. Combin. 4 (3) (2015), 11–23.
• [12] H. Wiener, Structural determination of the Paraffin Boiling Points, J. Amer. Chem. Soc. 69 (1947), 17–20.