ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 11 (2016) 247-254
Modified Wiener index via canonical metric representation, and some fullerene patches*
Modjtaba Ghorbani
Department of Mathematics, Faculty of Science, Shahid Rajaee, Teacher Training University, Tehran, 16785-136, I. R. Iran
Sandi Klavzar t
Faculty ofMathematics and Physics, University ofLjubljana, Slovenia Faculty of Natural Sciences and Mathematics, University ofMaribor, Slovenia Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia
Received 14 August 2015, accepted 27 October 2015, published online 30 November 2015
A variation of the classical Wiener index, the modified Wiener index, that was introduced in 1991 by Graovac and Pisanski, takes into account the symmetries of a given graph. In this paper it is proved that the computation of the modified Wiener index of a graph G can be reduced to the computation of the Wiener indices of the appropriately weighted quotient graphs of the canonical metric representation of G. The computation simplifies in the case when G is a partial cube. The method developed is applied to two infinite families of fullerene patches.
Keywords: Modified Wiener index, canonical metric representation, partial cubes, fullerene patches, nanocones.
Math. Subj. Class.: 05C12, 92E10
1 Introduction
The Wiener index is a central graph invariant in chemical graph theory as well as in metric graph theory, in the latter often being equivalently studied as the average distance. Several variations of the Wiener index were also extensively investigated, including the hyper-Wiener index and the terminal Wiener index. In 1991, Graovac and Pisanski [3]
* Research is supported by the Ministry of Science of Slovenia under the grant P1-0297. t Author to whom correspondence should be addressed.
E-mail addresses: mghorbani@srttu.edu (Modjtaba Ghorbani), sandi.klavzar@fmf.uni-lj.si (Sandi Klavzar)
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
248
Ars Math. Contemp. 11 (2016) 247-254
introduced the modified Wiener index with an idea to design a chemically applicable topological index which adequately takes into account the symmetries of a graph. The index received less attention than it deserves, but was studied recently by Koorepazan-Moftakhar and Ashrafi [13] where bounds on this graph invariant were obtained and exact values for some fullerenes.
Ten years after the seminal paper [3] an additional variation of the Wiener index was proposed in [15] and three years later named in [6] by the same term—the modified Wiener index. In the same paper the so-called variable Wiener index was also introduced; see the recent survey of Liu and Liu [14] on the variable Wiener index and related indices, especially on the related terminology. As it happens, also Graovac (see [16]) used the term modified Wiener index for the variation from [6, 15]. It is thus an unfortunate fact that the term modified Wiener index is nowadays used also for an invariant different from the one of Graovac and Pisanski. Anyhow, in this paper the term modified Wiener index is reserved for the original invariant. If the theory of this index will be more extensively developed in the future (for instance, it would be interesting to see how the invariant performs in the QSAR modelling for predicting physico-chemical properties of molecules), then the research community might wish to find a new name for it (to be honest, the terms "modified" and "variable" are not very descriptive), a possibility would be to call it the Graovac-Pisanski index.
We proceed as follows. In the next section concepts needed are formally introduced. The main result and its specialization to partial cubes are presented and proved in Section 3. In the final section we give closed expressions for the modified Wiener index of two infinite families of nanocones. These chemical graphs belong to the family of the so-called fullerene patches [4, 5].
2 Preliminaries
We denote the set {1,... ,n} with [n]. Unless stated otherwise, graphs considered are simple and connected. The distance dG(u, v) between vertices u and v of G is the usual shortest-path distance. A subgraph of a graph is called isometric if the distance between any two vertices of the subgraph is independent of whether it is computed in the subgraph or in the entire graph.
The Wiener index W(G) of G is the sum of distances between all pairs of vertices of G. A weighted graph (G, w) is a graph G = (V(G), E(G)) together with the weight function w : V(G) ^ R+. The Wiener index W(G, w) of (G, w), first introduced in [10], is:
W(G, w) = i ^^ ^^ w(u) w(v) do(u,v).
uev(G)vev(G)
Note that if w = 1 then W(G, w) = W(G).
The modified Wiener index W(G) of G was introduced in [3] as
T?(G)=2A|^ £ £ dG(u, a(u)), 1 v n ueV(G) aeAut(G)
where Aut(G) is the automorphism group of G. Roughly speaking, the modified Wiener index measures how far the vertices of a graph are moved on the average by its automorphisms.
M. Ghorbani and S. Klavzar: Modified Wiener index via canonical metric representation... 
249
The Cartesian product G □ H of graphs G and H is the graph with vertex set V(G) x V(H), where the vertex (g, h) is adjacent to the vertex (g', h') whenever gg' G E(G) and h = h', or g = g' and hh' G E(H).
If G is a graph, then the Djokovic-Winkler's relation © is defined on E(G) as follows: if e = xy G E(G) and f = uv G E(G), then e©f if d(x, u) + d(y, v) = d(x, v) + d(y, u). Relation © is reflexive and symmetric, hence its transitive closure ©* is an equivalence relation. The partition of E(G) induced by ©* is called the ©*-partition of E(G). Let G be a graph and let {F1,... ,Fk} be the ©* -partition of E (G). For any j G [k], let G/Fj be the graph whose vertex set consists of the connected components of the graph G - Fj, two components C and C' being adjacent if there exists an edge uv g Fj such that u G C and v G C'. Further, for any j G [k] let a.j : G ^ G/Fj be the mapping that assigns to each vertex of G the component of G - Fj to which it belongs. Now, the canonical metric representation of G is the (isometric) mapping a = (a1,... ,ak) : G ^ G/F\ □ • • • □ G/Fk. This mapping is due to Graham and Winkler [2]. The fundamental property of a from [2] that is essential for us is that a(G) is an isometric subgraph of G/Fi □ ••• □ G/Fk.
3 The main result
Our main result (Theorem 3.1) asserts that W(G) can be computed from the weighted Wiener indices of a collection of smaller graphs—the graphs of the canonical metric representation of G. Before stating the result we need to introduce the appropriate weighting functions.
Let G be a connected graph, let V\,... ,Vt be the orbits under the action of Aut(G) on V (G), and let F\,... ,Fk be the ©*-classes of G. For any i g [t] and any j G [k] define
wij : V(G/Fj) ^ R+ by setting
Wij(C) = |Vi n C|, C G V(G/Fj). We are now ready for the main result.
Theorem 3.1. Let G be a connected graph of order n and let V\,...,Vt be the orbits under the action of Aut(G) on V (G). If F\,... ,Fk are the ©*-classes of G, and G/Fj (j G [k]) and wij (i G [t], j G [k]) are as above, then
tk
W(G) = n £ — £ W(G/Fj ,Wij). i=1 1 il j=i
Proof. We first recall from [3, p. 57] that the modified Wiener index can be equivalently written as W (G) = nJ21=1 (W (Vi)/|Vi|). Hence we can write
_ t i
W(G)= nEr^ E do(x,y) .
i=1 1 {x,y}CVi
As already mentioned above, the canonical metric representation a is an isometry. Moreover, it is well-known (cf. for instance [7, Proposition 5.1]) that the distance function is additive on the Cartesian product operation, that is, dG □ H = dG + dH. These facts yield
250
Ars Math. Contemp. 11 (2016) 247-254
the first equality in the following computation:
t i k W(G) = nEn^" E J2dG/Fj (aj (x),aj (y))
i= 1 1 iI {x,y}CVi j= 1
= nE ¿i (E E dG/Fj (aj(x),aj(y))
i=1 1 J| \j=1 {x,y}CV
t 1 k /l
= nE r^E ( 2 E E dG/Fj (a(x),a(y))
i=1 1 j| j=1 \ xeVi yeVi tk
= n E n^ E W(G/Fj ,Wij). i=1 |Vi| j=1
To see the truth of the last equality, note that a pair of vertices x g Vi n C and y G Vi n C where C, C' are components of G-Fj, contributes dG/Fj (aj (x), aj (y)) to the summation. For each such pair of vertices the contribution is the same and there are wj (C) • wj (C') such pairs.	□
We note that a result parallel to Theorem 3.1 was earlier proved in [9] for the Wiener index, see [1,17] for applications of this result. It was recently further generalized twofold: to vertex-weighted graphs and to partitions coarser that the ©*-partition [11].
An important case containing many chemical graphs is the class of graphs isometrically embeddable into hypercubes; these graphs are known as partial cubes. It is well known that these graphs are precisely the connected bipartite graphs for which the relation © is transitive. Moreover, if F is an arbitrary ©-class (or, equivalenty, an arbitrary ©*-class) of G, then G - F consists of two connected components. It therefore follows that for partial cubes Theorem 3.1 can be simplified as follows:
Corollary 3.2. Let G be a partial cube of order n and let V1,..., Vt be the orbits under the action of Aut(G) on V(G). If F1,..., Fk are the ©-classes of G, and nj = |Vi n Cj n'ij = IV n Cj | (i G [t], j G [k]), where Cj and Cj are the connected components of G - Fj, then
t1k
W (G) =n E iVT E nij • nij. i=1 1 i| j=1
4 Modified Wiener index of two families of fullerene patches
To illustrate the applicability of Theorem 3.1 and Corollary 3.2 we determine in this section the modified Wiener index of two families of nanocones.
4.1 W of nanocones NCH(n)
The nanocones NCH(n), n > 1, are defined as follows. NCH(l) is isomorphic to the 6-cycle ("H" in the name stands for "hexagon"), while for n > 2, the nanocone NCH(n) is obtained from NCH(n - 1 ) by adding an additional outer ring of hexagons to it. The construction should be clear from Fig. 1 where NCH(4) is shown. (These nanocones are in chemical graph theory also known as the coronene/circumcoronene series.)
M. Ghorbani and S. Klavzar: Modified Wiener index via canonical metric representation... 
251
It is well-known that the nanocones NCH(n) are partial cubes (cf. [12]). Using Corollary 3.2 we can thus obtain the next result, a sketch of its proof being given in the rest of the subsection.
Theorem 4.1. If n > 1, then W(NCH(n)) = 3n3(10n2 - 1).
NCH(n) contains n concentric cycles (that is, the cycles iteratively added when the graphs is built from NCH(1)), call them the layers of NCH(n) and denote with L1,..., Ln. Clearly, |L,| = 12i-6,1 < i < n. Consequently, |V(NCH(n))| = £¡'=1(12i-6) = 6n2.
The ©-classes of NCH(n) are its orthogonal cuts, in Fig. 2 the horizontal cuts of NCH(4) are shown. In general, the cuts are in three directions and hence NCH(n) contains 3(2n - 1) ©-classes.
To apply Corollary 3.2 we also need to know the symmetries of NCH(n); we claim that the automorphism group of NCH(n) is isomorphic to the dihedral group D12 of order 12. To simplify the notation set r = Aut(NCH(n)). Let a be the rotation of NCH(n) for 60°, and let fi be the reflection of NCH(n) over the central vertical line. Clearly, r > (a, fi). On the other hand, if x is any vertex of the middle hexagon of NCH(n), then its orbit xr is formed by the vertices of the middle hexagon and its stabilizer rx consists of the identity and the reflection over the line through x and its antipode on the inner cycle. Hence
252
Ars Math. Contemp. 11 (2016) 247-254
|r| = |xr| x |rx| = 12. Since a6 = ¡32 = 1 and	= a-1, we conclude that r is
indeed isomorphic to D12. Note furthermore that each orbit of the action of r is a subset of some layer Lj, i e [n]. Moreover, the layer Lj contains i - 1 orbits of size 12 and one orbit of size 6.
For a graph G set
w(G) = W(G)/|V(G)|,
so that W(NCH(n)) = 6n2w(NCH(n)). Using the above description of orbits, Corollary 3.2, and considering the contributions of the vertices from Ln, a straightforward (but somehow lengthy) computation yields the recurrence
9
w(NCH(1)) = - ,
9
w(NCH(n)) = w(NCH(n - 1)) + 15n(n - 1) + -, n > 2 . The solution of this recurrence is w(NCH(n)) = 5n3 - n and Theorem 4.1 follows. 4.2 W of nanocones NCP(n)
The nanocones NCP(n), n > 1, are defined analogously as the nanocones NCH(n), except that now we start with a pentagon (hence the letter "P" in NCP) and then adding rings of hexagons to it. More precisely, NCP(1) is isomorphic to the 5-cycle, while for n > 2 the nanocone NCP(n) is obtained from NCP(n - 1 ) by adding an additional outer ring of hexagons to it. See Fig. 3 for NCP(4).
Figure 3: The nanocone NCP(4)
Since nanocones NCP(n) are not partial cubes, we cannot apply Corollary 3.2 for them, hence we need to use the more general Theorem 3.1 to get:
Theorem 4.2. If n > 1, then W(NCP(n)) = 5n3(11n2 - 2)/3.
In the rest of this subsection we give a sketch of the proof of this result. Just as for NCH(n), let us denote with L1,... ,Ln the layers of NCP(n). Since | Lj | = 10i - 5, i e [n], we get that |V(NCP(n))| = 10i - 5 = 5n2. The ©*-classes of NCP(n) can be described as follows. One class, say F, consists of the edges of the inner
M. Ghorbani and S. Klavzar: Modified Wiener index via canonical metric representation... 253
5-cycle together with the edges of the cuts propagating from them, see the left-hand side of Fig. 4. (The right-hand side of the figure shows the graph NCP(4) - F.) All the other ©*-classes of NCP(n) are the orthogonal cuts across hexagons. Since each additional layer defines five such cuts, the total number of ©*-classes is 1 + 5(n - 1) = 5n - 4.
Similarly as for NCH(n), the automorphism group of NCP(n) is isomorphic to the dihedral group D10 of order 10. Set r = Aut(NCP(n)), let a be the rotation of NCP(n) for 72°, and let 3 be the reflection ofNCP(n) over the central vertical line. Clearly, r > (a, ¡3). On the other hand, if x is any vertex of the middle pentagon of NCP(n), then its orbit xr is formed by the vertices of the middle pentagon and its stabilizer rx consists of the identity and the reflection over the line through x and the midpoint of the edge opposite to x. Hence |r| = |xr| x |rx| = 10. Since a5 = ¡2 = 1 and ¡-1 «¡3 = a-1, we conclude that r is isomorphic to D10. Furthermore, the layer Li, i e [n], contains i - 1 orbits of size 10 and one orbit of size 5. Using Theorem 3.1 and considering the contributions of the vertices from Ln, a straightforward computation yields
w(NCP (1)) = 3,
w(NCP(n)) = w(NCP(n - 1)) + 11n(n - 1) + 3, n > 2. The solution of this recurrence is w(NCP(n)) = (11n3 - 2n)/3 and Theorem 4.2 follows.
References
[1]	A.R. Ashrafi and Z. Mohammad-Abadi, On Wiener index of one-heptagonal nanocone, Current Nanosci. 8 (2012), 180-185.
[2]	R.L. Graham and P.M. Winkler, On isometric embeddings of graphs, Trans. Amer. Math. Soc. 288 (1985), 527-536.
[3]	A. Graovac and T. Pisanski, On the Wiener index of a graph, J. Math. Chem. 8 (1991), 53-62.
[4]	J.E. Graver and C.M. Graves, Fullerene patches, Ars Math. Contemp. 3 (2010), 109-120.
[5]	J.E. Graver, C. Graves and S.J. Graves, Fullerene patches II, Ars Math. Contemp. 7 (2014),
Figure 4: ©*-classes of NCP(3)
405-421.
254
Ars Math. Contemp. 11 (2016) 247-254
[6]	I. Gutman, D. VukiceviC and J. Zerovnik, A class of modified Wiener indices, Croat. Chem. Acta 77 (2004), 103-109.
[7]	R. Hammack, W. Imrich and S. KlavZar, Handbook of Product Graphs, Second Edition, CRC Press, Boca Raton, FL, 2011.
[8]	A. Kelenc, S. KlavZar and N. Tratnik, The edge-Wiener index of benzenoid systems in linear time, MATCH Commun. Math. Comput. Chem. 74 (2015), 529-540.
[9]	S. KlavZar, On the canonical metric representation, average distance, and partial Hamming graphs, European J. Combin. 27 (2006), 68-73.
[10]	S. KlavZar, Wiener number of vertex-weighted graphs and a chemical application, Discrete Appl. Math. 80 (1997), 73-81.
[11]	S. KlavZar and M.J. Nadjafi-Arani, Wiener index in weighted graphs via unification of ©*-classes, European J. Combin. 36 (2014), 71-76.
[12]	S. KlavZar and M.J. Nadjafi-Arani, Cut method: update on recent developments and equivalence of independent approaches, Current Org. Chem. 19 (2015), 348-358.
[13]	F. KoorepaZan-Moftakhar and A.R. Ashrafi, Distance under symmetry, MATCH Commun. Math. Comput. Chem. 75 (2015), 259-272.
[14]	M. Liu and B. Liu, A survey on recent results of variable Wiener index, MATCH Commun. Math. Comput. Chem. 69 (2013), 491-520.
[15]	S. Nikolic, N. Trinajstic and M. Randic, Wiener index revisited, Chem. Phys. Lett. 333 (2001), 319-321.
[16]	D. Vukicevic and A. Graovac, On modified Wiener indices of thorn graphs, MATCH Commun. Math. Comput. Chem. 50 (2004), 93-108.
[17]	Z. Yarahmadi and G.H. Fath-Tabar, The Wiener, SZeged, PI, vertex PI, the first and second Zagreb indices of N-branched phenylacetylenes dendrimers, MATCH Commun. Math. Comput. Chem. 65 (2011), 201-208.