ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 15 (2018) 441-466
https://doi.org/10.26493/1855-3974.1297.c7c
(Also available at http://amc-journal.eu)
The Hosoya polynomial of double weighted
graphs*
*
Tina Novak, Darja Rupnik Poklukar, Janez Žerovnik t
University of Ljubljana, Faculty of Mechanical Engineering, Aškerčeva 6, SI-1000 Ljubljana, Slovenia
Received 18 January 2017, accepted 16 December 2017, published online 18 August 2018
The modified Hosoya polynomial of double weighted graphs, i.e. edge and vertex weighted graphs, is introduced that enables derivation of closed expressions for Hosoya polynomial of some special graphs including unicyclic graphs. Furthermore, the Hosoya polynomial is given as a sum of edge contributions generalizing well known analogous results for the Wiener number. A linear algorithm for computing the Hosoya polynomial on cactus graphs is provided. Hosoya polynomial is extensively studied in chemical graph theory, and in particular its weighted versions have interesting applications in theory of communication networks.
Keywords: Wiener number, Hosoya polynomial, Wiener polynomial, edge contributions, communication network, cactus graph, linear algorithm.
Math. Subj. Class.: 05C12, 92E10, 68R10
1 Introduction
The Hosoya polynomial was first studied by Hosoya [12], and later introduced independently under the name Wiener polynomial [20], perhaps because of its property that the first derivative of the polynomial evaluated at x = 1 equals the Wiener number. The name Hosoya-Wiener polynomial may be a good compromise [25, 26], however the majority of researchers nowadays use the term Hosoya polynomial. The main advantage of the Hosoya polynomial is that it contains a wealth of information about distance based invariants. Besides the above mentioned relation to the Wiener number, natural relations to other
* Work supported in part by ARRS, Research Agency of Slovenia.
t Corresponding author. Also part time researcher at IMFM, Jadranska 19, Ljubljana, Slovenia.
E-mail addresses: tina.novak@fs.uni-lj.si (Tina Novak), darja.rupnik@fs.uni-lj.si (Darja Rupnik Poklukar), janez.zerovnik@fs.uni-lj.si (Janez Zerovnik)
Abstract
©® This work is licensed under https://creativecommons.Org/licenses/by/3.0/
442
Ars Math. Contemp. 15 (2018) 441-466
indices are known including the hyper-Wiener index [3] and Tratch-Stankovich-Zefirov index [1, 10]. The Hosoya polynomial has been investigated on many special classes of graphs, and vast literature includes some very recent studies, for example [4, 7, 14, 16].
The Hosoya polynomial generalizes nicely to the weighted graphs, as noted already in [25]. It seems that many properties of the polynomial remain valid in the weighted case, starting with the relations to the weighted Wiener number and hyper-Wiener index [25]. It may be interesting to note that the Wiener number, the polynomial and the corresponding generalizations also have natural applications in theory of communication networks, because the distance properties of a graph are of central importance there [6, 8, 18, 24]. In [26], a recursive formula for the Hosoya polynomial is derived yielding a linear time algorithm for computing the polynomial on trees. A generalization to cactus graphs was left as an open problem in [26]. The main motivation for this work was to design a linear algorithm for the Hosoya polynomial on double weighted cactus graphs. To achieve the main objective, we provide some auxiliary structural results that may be of independent interest, for example we show how the polynomial of a graph with cut edge can be expressed in terms of certain polynomials of the subgraphs (Lemma 4.1). Analogous results are given for graphs with cut vertex (Lemma 4.4) and for graphs generalizing unicyclic graphs (Lemma 5.1). As a related result that may be of independent interest, we show how the Hosoya polynomial can be expressed in terms of edge-contributions. Again, this may be of particular importance in theory of communications, as the edge contributions are under some natural assumptions directly related to communication load of edges (i.e. communication links). Finally, we outline a linear algorithm for computing the Hosoya polynomial on double weighted cactus graphs. More precisely, our algorithm is linear in the number of basic operations on polynomials i.e. addition and multiplication of polynomials.
The rest of the paper is organized as follows. In the next two sections some basic definitions including the definition of Hosoya polynomial are recalled. In Section 4, the Hosoya polynomials of some special graphs are calculated. In Section 5, cycle-like graphs are considered. For later use, the "modified Hosoya polynomial" of two variables is introduced. In Section 6, the Hosoya polynomial is expressed in terms of edge contributions. In Section 7, the algorithm for calculating the Hosoya polynomial is outlined in some details and its linear time complexity is shown.
2 Definitions
A double weighted graph G = (V, E, w, A) is a combinatorial object consisting of an arbitrary set V = V(G) of vertices, a set E = E(G) of unordered pairs {u, v} = uv = e of distinct vertices of G called edges, and two weighting functions, w and A. The weight function w: V(G) ^ IR+ assigns positive real numbers (weights) to vertices and the distance function A: E(G) ^ IR+ assigns positive real numbers (lengths) to edges. The order and size of G are n = | V(G) | and m = |E(G) |, respectively.
A path P between u and v is a sequence of distinct vertices u = vj, vi+1, ..., vk-1, vk = v such that each pair v^l+1 is connected by an edge. The length of the path P is the sum of the lengths of its edges,
k_i
*(P) = E A(vivi+i).
i=i
The distance dG(u, v), or simpler d(u, v), between vertices u and v in graph G is the length
T. Novak et al.: The Hosoya polynomial of double weighted graphs
443
of a shortest path between u and v. If there is no such path, we write d(u, v) = to. The diameter of a graph G is the maximal distance in G, D(G) = maxu,veV(G) dG(u, v).
A graph G is connected if d(u, v) < to for any pair of vertices u, v G V(G). A vertex v is a cut vertex if after removing v and all edges incident to it the resulting graph is not connected. A graph without a cut vertex is called nonseparable. A block is a maximal nonseparable graph. Here, a cycle is an induced subgraph which is connected and every vertex is of degree two. A cactus is a graph in which every block of three or more vertices is a cycle. We also can say that cactus is a graph in which every edge is a part of at most one cycle.
The weighted Wiener number of a weighted connected graph G is defined as
W(G) = ^ w(u)w(v)d(u, v).
{u,v}CV (G)
This is obviously a generalization of the usual definition of (unweighted) Wiener number, the sum of distances over all unordered pairs of vertices of G. The definition also generalizes the definition of the Wiener number for vertex-weighted graphs as used in [13]. Let us only mention that the Gutman index or the Schultz index of the second kind [9], where the weights of vertices are their degrees, is listed in [15] as an example of weighted versions of the Wiener index.
3 The Hosoya polynomial
A notion closely related to the Wiener number is the Hosoya polynomial of a graph G which is defined as
H (G,x) = ^ xd(u'v),	(3.1)
u,v£V (G)
where the sum runs over all unordered pairs of vertices u,v G V(G). This definition, which is used for example in [11], slightly differs from the definition used by Hosoya [12]:
F(G,x) = ^ xd(u'v).	(3.2)
{u,v}CV (G)
Obviously, H(G, x) = H"(G, x) + |V(G)|, because in (3.2) the sum runs over all unordered pairs {u, v} of distinct vertices (u, v G V(G), u = v), while in (3.1) u and v need not be distinct.
The Hosoya polynomial of a weighted graph G is defined as
F(G,x)= ^ w(u)w(v) xd(u'v),	(3.3)
{u,v}CV (G)
where the sum runs over all unordered pairs {u,v} of distinct vertices (u,v G V(G), u = v), as in definition (3.2). In the case when all weights of edges and vertices equal 1, we get the Hosoya polynomial as usually defined for unweighted graphs.
Remark 3.1. If G is a graph with one vertex and no edges, G = {v}, we define
#({v},x) := 0.
(3.4)
444
Ars Math. Contemp. 15 (2018) 441-466
Note that H(G, x) may not be a polynomial if edge lengths are allowed to be arbitrary real numbers. Obviously, if positive integers are used for edge lengths, the function H(G, x) is a polynomial. Hence, with appropriate scaling factor, we can always consider H(G, x) to be a polynomial, for any model using rational edge lengths.
The Hosoya polynomial has many interesting properties [10, 12, 25], perhaps the most interesting of them is that its derivative at 1 equals the Wiener number.
For a connected graph G with more than one vertex, denote the modified Hosoya polynomial by
M (G,x)=	d(u,v)w(u)w(v)xd(u'v).
{u,v}ÇV (G)
(3.5)
Then clearly,
M(G,x) = x • — H(G,x), ax
and
H(G,x) =
M (G,t)
t
dt.
Later we will use the contributions of a vertex to the Hosoya polynomial. More precisely, we denote the contribution of all paths from a fixed vertex a to all vertices of some subgraph H of G (it is also possible a e H) by
x
0
Ha(H,x)=	w(a)w(v) xd(a'v) = w(a) ^ w(v) xd(a'v) (3.6)
vev(H )	vev (H)
and
Ma(H,x)=	d(a,v)w(a)w(v) xd(a'v) = w(a) ^ d(a,v)w(v) xd(a'v).
vev (h)	vev (h)
Obviously,
Ha({a},x) = w(a)2, Ma({a},x)=0
and
H(G,x) = 2 ^ (-Ha(G,x) - w(a)2) .
aev (G)
Remark 3.2. Note that Ha(G, x) may be regarded as a natural generalization of "partial Wiener polynomial" Ha(G, x) used by Doslic [5] on unweighted graphs. More precisely,
Ha(G, x)= ^ w(a)w(v) xd(a'v) = Ha(G, x) - w(a)2 . (3.7)
veV (G),v=a
4 Auxiliary results
Following the idea of [17], we calculate the Hosoya polynomial of some special examples of weighted graphs from the Hosoya polynomials of the given subgraphs. For later reference, auxiliary polynomials Ha(G, x), i.e. the contributions of all paths from fixed vertex a to all vertices of G, are also explicitly evaluated. Until further notice, the subgraphs considered are assumed to have at least one edge.
T. Novak et al.: The Hosoya polynomial of double weighted graphs
445
Lemma 4.1. Let Ga and Gb be disjoint rooted graphs with roots a and b respectively, and let G be a disjoint union of Ga and Gb by the edge e = ab, see Figure 1. Then the Hosoya polynomial of G equals to
H(G, x) = H(Ga, x) + H(Gb, x) +
1
and
w(a)w(b) w(a)
Ha(Ga,x) Hib(Gb, x) x
He)
Ha(G, x) = Ha(Ga,x) +--— Hb(Gb,x) x
w(b)
Me)
Proof.
Figure 1: A graph with a bridge.
H(G,x) =	w(u)w(v)xd(u'v) =	w(u)w(v)xd(u'v) +
{u,v}CV(G)	{u,v}CV(Ga)
+ ^ w(u)w(v)xd(u'v) + ^ w(u)w(v)xd(u'v)
{u,v}CV (Gb)
uev (Ga) vev (Gb)
It is obvious that first two sums equal to H(Ga, x) and H(Gb, x), respectively. Furthermore, observe that
1
w(a) 1
Ha(Ga,x)=	w(u)x
uev (Ga)
Kb)'
Hb(Gb, x)	w(v)x
,d(u,a)
,d(b,v)
vev (Gb)
and
rHa(Ga,x) • Hb(Gb,x)= ^ w(u)w(v) w(a)	w( b)
w(u)w(v)x
d(u,a) + d(b,v)
uev (Ga ) veV(Gb)
1
446
Ars Math. Contemp. 15 (2018) 441-466
Thus
xx(e) ■Ha(Ga,x) ■ —Hb(Gb,x)= V w(u)w(v)x w(a)	w(b)	z—'
w	w	uev (Ga)
vev (Gb)
since
d(u, a) + X(e) + d(b, v) = d(u, v).
d(u,v)
Similarly,
Ha(G, x) = w(a) w(v)x
d(a,v)
veG
= w(a) ^ w(v)xd(a'v) + w(a) ^ w(v)xd(a'v) = veGa	veGb
= Ha(Ga,x) + w(a)-^-Hb(Gb,x) xx(e).	□
w(b)
Example 4.2. Let Gb = {b}, Ga = {a} and G = {a, b} U ab (see Figure 2, left). From the definition (3.3) of the Hosoya polynomial it follows H(G, x) = w(a)w(b)xx(ab). On the other hand, using Lemma 4.1 we get (the initial values for vertices a and b are determined as in (3.4)):
H(G, x) = H(Ga, x) + H(Gb, x) + 1 Ha(Ga, x) Hb(Gb, x) xx(ab) =
w( a) w( b)
= 0 + 0+ , } „, w(a)2w(b)2xx(ab). w(a) w(b)
Figure 2: A graph G with two vertices (left), a rooted graph G with a bridge (right).
Example 4.3. Let Gb = {b} and Ga be an arbitrary rooted graph, such that b V(Ga). Let G be the rooted graph G = Ga U {b} U ab (see Figure 2, right). Using Lemma 4.1 and
T. Novak et al.: The Hosoya polynomial of double weighted graphs	447
equation (3.4)
H(G, x) = H(Ga, x) + H(Gb, x) + . 1 ... Ha(Ga, x) Hb(Gb, x) xx(ab) =
w(a)w(b)
= H(Ga, x) + 0 + 1 Ha(Ga, x) w(b)2 xX(ab) = w(a)w(b)
d(v,a) + X(ab)
= H(Ga,x) + w(a)w(b) xx(ab) + w(b) ^ w(v)x
vev (Ga)
v = a
Lemma 4.4. Let G\ and G2 be graphs with one common vertex a and let G\ — a and G2 — a be disjoint. If G = G\ U G2 (see Figure 3), the Hosoya polynomial of the graph G equals to
H(G, x) = HI(Gl,x) + H(G2, x) +
+ wOy (Ha{Gi,x) — w(a)2) (Ha{G2,x) — w(a)2j
and
Ha(G,x) = Ha(Gux) + Ha(G2,x) — w(a)2.
Figure 3: Two graphs with a common vertex.
Proof. Similarly to the proof of Lemma 4.1, we have
H(G,x) = ^ w(n)w(v)xd(u'v) =
{u,v}CV (G)
= ^ w(u)w(v)xd(u'v) + ^ w(u)w(v)xd(u'v) +
{u,v}CV(Gi)	{u,v}CV (G2)
+ ^ w(u)w(v)xd(u>a)+d(a>v) — ^ w(u)w(a)xd(u'a) —
uev(Gi)	uev (Gi)
vev (g2)
- J2 w(a)w(v)xd(a,v) + w(a) vev (G2)
448
Ars Math. Contemp. 15 (2018) 441-466
= H(Gux)+ H(G2,x) +
. Ha(Gl,x) Ha(G2,x) urn \ u in \ i f \2
+-----T^--Ha(Gi,x) - Ha(G2, x) + w(a) =
w(a)	w(a)
= H(Gi, x) + ii(G2, x) + (Ha(Gi, x) - w(a)2) (iia(G2, x) - w(a)2) . We used the fact that, because G1 and G2 share the vertex a,
E = E + E .
ueV(G 1) ueV(G 1) u=v=a veV (G2) v£V (G2)
u=v
The second equation holds because
HHa (G,x)= ^ w(a)w(v)xd(a'v) =
veV (G)
= E w(a)w(v)xd(a'v) + E w(a)w(v)xd(a'v) - w(a)2 = v£V (Gi)	veV (G2)
= Ha(Gi,x)+ Ha(G2,x) - w(a)2.	□
Remark 4.5. The statement of Lemma 4.4 is a generalization of Theorem 2.1 from [4] for the case when two double weighted connected graphs Gi and G2 are point-attached to obtain G. However, it is easy to see that Lemma 4.4 can be generalized to the general case with any finite number of graphs. As the proof is short, we write and prove the following theorem for completeness of presentation.
Theorem 4.6. Let Gi be graphs with one common vertex a and let Gi - a be disjoint. If
g=u n
= 1 Gi, the Hosoya polynomial of the graph G equals to
n
H(G, x) = E HH(Gi, x) +
i=i
and
n
Ha(G, x) = E Ha(Gi,x) - (n - l)w(a)2.
i=i
Proof. For n = 2 the result follows from Lemma 4.4, and for arbitrary n the result follows by induction. Suppose the equation (4.1) is valid for n - l, let Go = Un-11 Gi and G =
T. Novak et al.: The Hosoya polynomial of double weighted graphs	449
G0 U Gn. Then, using Lemma 4.4,
+ w(a)2 (Ha(Go,x) - w(a)2j (Ha(Gn,x) - w(a)2^j
H(G, x) = H(G0, x) + H(Gn, x) + 1
w(a) 2
n-1
= Y H(Gi,x)+H(Gn,x) + i=i
n-2 n-1 i
+ YY W{a)^(^a(Gi,x) - w(a)2^ (Ha(Gj,x) - w(a)2^ +
i=1 j=i+1 n-1
w(a) 2
W v i=1
+ Wla^i ( Y ^a(Gi, x)) - (n - 2)w(a)2 - w(a)2) (Ha(Gn, x) - w(a)2) =
n-2 n-1 1
Y H(Gi,x) + Y Y wUrfftaG ,x) - w(a)2^( Ha(Gj ,x) - w(a)2) +
/ \2 \ ^a( w( a) 2
w(a)2
= 1 i=1 j=i+1 v ' n-1 i
+ Y w(a)2 i^a(Gi,x) - w(a)2) (jia(Gn,x) - w(a)2) =
1
n 1 n
i=1 i=1 j=i+1
and
Y H(Gi,x) + Y Y wia]2(^a(Gi,x) - w(a)2^(Ha (Gj ,x) - w(a)2^j
Ha(G,x) = Ha(Go,x) + Ha(Gn,x) - w(a)2 =
n-1
Y Ha(Gi,x) - (n - 2)w(a)2 + Ha(Gn,x) - w(a)
i=1
n
2
Y Ha(Gi,x) - (n - 1)w(a)2 . □ 1
5 Cycle-like and unicyclic graphs
We now consider the case when the specific vertices a1,a2,... ,an in G are vertices of a cycle.
Lemma 5.1. Let Gai, Ga2,..., Gan be disjoint rooted graphs and denote by GC the union of Gai, Ga2,..., Gan, joined by the edges a1a2, a2a3,..., an-1an and ana1, see Figure 4. In this case the Hosoya polynomial of GC equals to
H(GC, x) = Y H(Ga
lC,x) = > n(Gai,x) 1
n 1 n
+	< W A (Gai ,x) ■ Haj (Gaj ,x) ■ xd(ai>a > (5.1)
i=1 j=i+1 w(ai)w(aj) j j
450
Ars Math. Contemp. 15 (2018) 441-466
and
Hai (GC,x) = Ha (Gai ,x) + V ^Hj (Gj ,x) ■ xd(aia j
j=1 w(«j )"
j=i
for every i = 1, 2,... ,n.
Figure 4: A cycle-like graph GC.
Remark 5.2. In Lemma 5.1, the graph GC can be any connected graph with a cycle such that all vertices a1,a2,... ,an of the cycle C are cut-vertices, and the Gai can be any subgraphs. Clearly, this includes as a special case the unicyclic graphs.
Proof of Lemma 5.1. Following the idea of the proof of Lemma 4.1, we write
H(GC ,x)= ^ w(u)w(v)xd(u'v) =
{u,v}C V (G)
n— 1 n
J2	w(n)w(v)xd(u'v) + ^ J2 J2 w(u)w(v)x
d(u,v) _
= 1 {u,v}CV (Gai)
=1 j=i+1 uev (Gai) vev (g„.)
n 1 n
Y,H(Gai +	Hai (Gai , x) ■ xd(ai>a) ■ Ha, (Ga, , x)
i=1
i=1 j=i+1
w(ai)"
w(aj)
and
Hai (GC, x) =	w(ai)w(v)x
vev (G)
d(ai,v) _
^^ w(ai)w(v)xd(ai'v) + ^^ ^^ w(ai)w(v)x
d(ai )+d(a, ,v)
vev (Gai)
j=1vev (g) j=i j
T. Novak et al.: The Hosoya polynomial of double weighted graphs
451
= (Gai,x) + V Ha, (Ga, ,x) • xd(ai'a>>,
z—' w(aj) J J
j=i
as claimed in Lemma 4.1.	□
Example 5.3. Let C be a cycle on three vertices a, b and c, with edges ab, bc and ca (see Figure 5). From Lemma 5.1 it follows
H(C, x) = H(Ga, x) + H(Gb, x) + H(Gc, x) +
+ , * Ha(Ga,x)Hb(Gb,x)xx(ab +
w(a) w( b)
+ nl . . Hb(Gb,x)Hc(Gc,x)xx(bc) + . 1 . . Hc(Gc,x)Ha(Ga,x)xx(ca) = w(b) w(c)	w(c) w( a)
= w(a)w(b)xx(ab) + w(b)w(c)xx(bc) + w(c)w(a)xx(ca).
The result is the same as expected, from the definition (3.3). A similar reasoning applies to larger cycles.
Figure 5: A cycle graph C.
Recall that our original motivation was to design a linear algorithm for calculating the Hosoya polynomial of a cactus graph. Observe that from equation (5.1) it appears that a double sum needs to be calculated which yields quadratic complexity. Therefore, we are going to consider this case more carefully and provide an alternative expression that will later be used to show the existence of a linear algorithm.
First, we will consider path-like graphs, and introduce, for technical reasons, polynomials of two variables that will in turn allow a natural generalization to handle cycle-like graphs.
Let GP be a path-like graph, i.e. the union of disjoint graphs Gai ,Ga2,... ,Gan, rooted at a1,a2,... ,an respectively, and joined by the edges aia2, a2a3,. .., an-1 an. The Hosoya polynomial H(GP, x) and the polynomial Han (GP, x) can be calculated recur-
452
Ars Math. Contemp. 15 (2018) 441-466
sively using Lemma 4.1 (n - 1) times. For such a path-like graph GP, we use the notation
Hi — Ga
i i
j
Hj — Gai U jaia2, a2a3,. .., a,j-ia,j} , 1
where GP = Hn. By Lemma 4.1, the Hosoya polynomial and the corresponding polynomials Haj are, for j = 1:
H(Hux) — H(Gai ,x), Hai (Hi,x) — Hai (Gai ,x),
and, for j > 1:
H(Hj, x) — H(Ga, ,x) + H(Hj—i,x) +
+ Wjj) Haj (Gaj ,x)Haj-i j ^^ '
Ha, (Hj ,x) — Haj (Gaj ,x) +	Ha;-i (Hj — i, x)xX(a>-ia> > .
w(aj—i)
The recursion above implies that, given polynomials H(Gai,x) and Hai(Gai,x), i = 1,2,..., n, we need 3(n - 1) additions and 2(n - 1) multiplications (of polynomials) to obtain all H(Hi, x) and Ha. (Hi, x).
From the definition of the graphs Hi and the recursions written above, we also have
Lemma 5.4. For the graphs Hj, j = 2,... ,n, the following is true
3
H(Hj ,x)=Y, H(Gai ,x) + = 1
j-l j
+ } ^ } ^ / \ / \ Hai (Gai ,x)Hae (Gaf, x)x^~jk i ( + ),
h Ai w(ai)w(a^)
j—i ( )
Haj (Hj ,x) — Ha, (Ga, ,x)+Y, Hai (Gai, x)^ k-i X(a"ak+i ) .
Proof. Lemma follows directly by the induction on j, using Lemma 4.1 and the recursive formulae above.	□
Before generalizing from path-like to cycle-like graphs, we introduce auxiliary polynomials of two variables. For technical reasons, to distinguish the exponents based on the distance on the path and off the path, i.e. the exponents based on the distance within the graphs Ga1, we introduce a second variable y. For example, assume that a shortest path from u G V(Gai) to v G V(Gaj) has distance d(u, v) — d(u, ai) + d(ai, aj) + d(aj, v). Then the contribution to the auxiliary polynomial is w(u)w(v)xd(u'ai)yd(ai'aj)xd(aj'v).
T. Novak et al.: The Hosoya polynomial of double weighted graphs
453
More formally,
j
H(Hj ,x,y):=YJ H(Gai , x) +	(5.2)
3 yj- / , " v a.
i=i
j-i	3	I
+ E E ( ) ( )HHai(Gai,x)Ha,(Ga,,x)y^=^fc+O, 1=1"(ai)"(ai) 3-1 ( )
Ha, (Hj, x, y) := Ha. (Gaj, x) + £ wa)iHai (Gai, x^^ *(akak+1) .
i=1 "(ai)
After the introduction of the new variable y, the recursion formulae become
F(Hi,x,y) = H(Ga! ,x),	(5.3)
Hax (Hi,x,y)= HHai (Ga!, x)	(5.4)
for j = 1 and at every step of the recursion we have
H(Hj, x, y) = F(Ga3 ,x) + HH"(Hj-i, x) +	(5.5)
+ "T^W-THa, (Ga, ,x)Ha,._i (Hj-i, x^-^),
w(a3- )w(a3--i) j j	j j
Haj (Hj, x, y) = Ha, (Ga,, x) + ""03-Ha,- (Hj-i, x)yA(aj-iaj) .	(5.6)
^^ (aj_i)
It is obvious that
H(Hj, x, x) = H(Hj, x) and Ha, (Hj, x, x) = Ha, (Hj, x).
Let GC be a cycle-like graph, i.e. the union of disjoint graphs Gai, Ga2,..., Gan, rooted at ai, a2,..., an respectively, and joined by the edges aia2, a2a3, .. ., an-ian and anai. Denote by L the girth of the cycle C on vertices ai, a2,..., an, specifically
L = A(a„ai) + ^ A(ajai+i) .
^-1
" (ai
i=i
Define new modified polynomials of two variables of the path-like graph GP as follows
Fm(GP, x, y) := Y, Hi (Gai ,x) + i
n-1 n	£-i	£-i
E	1	min^ A(afcafc + i),L- £ A(akak+i)}
, ^ , , H(Gai,x)if(Ga,, x)y k=i	k=i	,
HHrn (GP, x,y) := Han (Ga„ ,x) +
n — 1 "-i "-i
Ew(an) H	min{ E x(akak+i),L- J2 ^(afcafc+i)}
, \ Hai (Gai ,x)y fc=i	fc=i	.
"(a»)
i=i
According to Lemma 5.1, the next statement is obvious.
454
Ars Math. Contemp. 15 (2018) 441-466
Proposition 5.5.
Hfm(GP,x,x) = F(GC,x) and HH^(GP,x,x) = Han(GC,x).
Example 5.6. Let GC be a cycle-like graph which is the union of disjoint graphs Gai, Ga2, Ga3 and Ga4 and edges &1&2, ^2^3, and We assume that the polynomials
HHa. (Ga., x) and H"(Gai,x) are given and that A(aia2) = 2, A(a2a3) = 5, A(a3a4) = 3 and A(a4ai) = 1 as we see in Figure 6. In this case L = 11. The computations below
a4
a 1
	a4	ai	
3			2
	la3	a2	
Figure 6: A cycle-like graph with given lengths of cycle's edges.
are following the recursion for the path-like graph and the idea of the separation of the exponents, and, in addition, we observe that the distances on the path change when the path is closed to a cycle with the edge a4a1. The base of the recursion is
HHai (Hi, X, y) = HHai (Gai ,x), #(#i,x,y) = Hi (Gai ,x).
Other steps are clearly
HHa 2 (H2,x,y) = HHa 2 (Ga2, x) +	HHai (Hi,x,y)y2 =
w(ai)
= Ha2 (Ga2 , x) + ( )HHai (Gai , x)y^
w(ai)
Hf(H2, x, y) = F(Ga2, x) + Hi (Hi, x, y) +
+--;—^—7HHa2 (Ga2, x)HHai (Hi, x, y)y2
1
w(a2)w(ai) Hi(Ga2 ,x) + Hf(Gai , x) +
w(a2)w(ai)
Ha2 (Ga2 ,x)Hai (Gai , x)y ,
HHa3 (H3, x, y) = HHa3 (Ga3, x) +	H^ (h-2,x, y)y5 =
w(«2)
= HHa3 (Ga3 , x) + w(°3) Ha2 (Ga2 , x)y5 + ^i^3!HHai (Gai , x)y7,
w(«2)
w(ai)
T. Novak et al.: The Hosoya polynomial of double weighted graphs
455
H(H3,x,y) = H(Ga3 ,x) + H(H2,x,y) +
+ —,-^-7Ha3 (Ga3 ,x)Ha2 (H2,x,y)y"5 =
w(a3)w(a2)
= H(Ga3, x) + H(Ga2, x) + H(Gai, x) +
+--7—^—rHal (Gal, x)Ha2 (Ga2, x)y2 +
w(a2)w(ai)
+ 7 \ 7 Ha3 (Ga3 ,x)Ha2 (Ga2 , x)y +
w(a3)w(a2)
+ 7 \ 7 THa3 (Ga3 , x)Hai (Gai , x)y ■
w(a3)w(a\)
Similarly,
w
(a4)
Ha4 (H4, x, y) = Ha4 (Ga4, x) +---—-Ha3 (H3,x,y)y =
w(a3)
= -Ha4 (Ga4 , x) +	Ha3 (Ga3 , x)y3 +
w(a3)
+ ^ Ha2 (Ga2 , x)y8 + ^ Hai (Gai , x)y10 w(a2)	w(ai)
and
H(H4 ,x,y)= H(Ga4 ,x) + H(H3,x,y) +
+ , \ , . Ha 4 (Ga4 ,x)Ha3 (H3 ,x,y)y3 = w(a4 )w(a3)
= H(Ga4, x) + H(Ga3, x) + H(Ga2, x) + H(Gai , x) +
+ 7 n 7 rHai (Gai , x)Ha2 (Ga2 , x)y'2 +
w(a2)w(ai)
+ 7	7 ^Ha3 (Ga3 ,x)Ha2 (Ga2 ,x)y +
w(a3)w(a2)
+--7-^-rHa3 (Ga3 , x)Hai (Gai , x)y7 +
w(a3)w(ai)
+ , 1 , , Ha4 (Ga4 , x)Ha3 (Ga3 , x)y3 + w(a4)w(a3)
1
+ 7 \ 7 rHa4 (Ga4 , x)Ha2 (Ga2 , x)yS + w(a4)w(a2)
+ 7-n-7-r Ha4 (G a4 , x)Hjai (Gai , x)yW ■
w(a4)w(ai)
Than the modified polynomials of two variables are
Hm (H4, x, y) = Ha4 (Ga4 , x) +	Ha3 (Ga3 , x)y3 +
4	w(a3)
, w(a4) jj tr, ,3. w(a4) jj (n s
+--7—r H a2 (Ga2 ,x)y +--—T Hai (Gai, x)y
w(a2)	w(ai)
456
Ars Math. Contemp. 15 (2018) 441-466
= HH04 (G04, x) + ^Ç^. Hai (Gai, x)y + w(ai)
+ (	Ha3 (Ga3 ,x) +	Ha2 ^ ,x))y3
vw(a3)	w(a2)	/
and
íím(Hi, x, y) = HÍ(Ga4, x) + Hi(Ga3 , x) + H(Ga2 , x) + i/(Gai, x) +
+ 7 Ñ 7 rHHa1 (Ga1, x)Ha2 (Ga2 , x)y2 +
w(a2)w(ai)
+ 7 \ 7 Ha3 (Ga3 , x)Ha2 (Ga2 , x)y +
w(a3)w(a2)
+--7-^-rHHa3 (Ga3 , x)HHai (Gai, x)y4 +
w(a3)w(ai)
+--7-^-rHa4 (Ga4 ,x)HHai (Gai, x)y1 +
w(a4)w(ai)
+ ( —7-Ñ-7-7Ha4 (Ga4 ,x)HHa3 (Ga3 , x) +
yw(a4)w(a3)
+ , w ^ HHa4(Ga4, x)HHa2 (Ga2,xn y3.
w(a4)w(a2 )	/
Hence, the Hosoya polynomial and the polynomial Ha4 (Gc, x) are
H~(GC,x)= iim(H4,x,x) and Ha4(GC,x) = H^(H4,x,x).
Observe that the time complexity of the transformation of a polynomial of two variables x and y to the polynomial of one variable x (where y ^ x) is comparable to time complexity of multiplication of polynomials. Thus, we can conclude:
Theorem 5.7. The Hosoya polynomial of a cycle-like graph can be computed using the recursion (5.3), (5.4), (5.5), (5.6) in linear time, in the model where addition and multiplication of polynomials are atomic operations.
6 The Hosoya polynomial in terms of edge contributions
It is well-known that the Wiener number can be expressed as a sum of edge contributions, see for example [19]. Recall, for example, the version for weighted graphs.
Lemma 6.1 ([22]). For a weighted graph G,
-y n*(
n;(a, b)
W(G) = £ A(e) • £ ^^ w(a)w(b),

where 9 e denotes a shortest path between a and b, n*(a, b) is the number of shortest paths with endpoints a and b and n*(a, b, e) is the number of all shortest paths with endpoints a and b traversing edge e.
T. Novak et al.: The Hosoya polynomial of double weighted graphs	457
Hence, the quotient "„i^bf represents the proportion of all shortest paths between a in b including e, among all shortest paths between a and b. On a tree, there is a unique shortest path between any pair of vertices, thus n*(a, b, e) = n* (a, b) = 1 for all a, b. If G is a cactus graph, "„i""^ can only have value 1 or 1. Clearly, "„i""^ = 1 exactly when a and b are opposite vertices of a cycle and edge e is on this cycle. (More precisely, with opposite vertices of a cycle we mean that d(a, b) = L/2 where L is the girth of the cycle.)
It may be interesting to note that this formulation has an interesting meaning when considering the weighted graphs as communication networks [6, 18, 24]. In this case the Wiener number is interpreted as the total communication traffic in the network, where naturally the communication between nodes u and v contributes d(u, v)w(u)w(v) (distance times population sizes of the two nodes). Assuming that all the communication is routed on the shortest paths and that it is evenly distributed among shortest paths if there are many of them, the edge contribution corresponds to the communication load on the edge.
Example 6.2. Let G be a communication network represented in Figure 7, where all edges have lengths 1. There are exactly three shortest paths between vertices u and v. Ratios indicating the part of the communication load are attached to the edges on the shortest paths.
As shown in [26], the Hosoya polynomial can be represented as a sum of the contributions of all shortest paths:
Lemma 6.3 ([26]). For a weighted graph G,
1	^	T-r A(e)
h(g,X)= y, Y,n*(a b) w(a)w(b) nX
{a,b}ÇV(G) Pfb ( , )	eePfb
where P*b denotes a shortest path between a and b and n*(a,b) is the number of all shortest paths with endpoints a and b.
Representing the Hosoya polynomial in terms of edge contributions is hence somewhat more complicated: For each path crossing the edge, one needs to know the amount of traffic (the intensity of the traffic corresponds to „ „(" b) w(a)w(b)) but also the length of the paths.
458
Ars Math. Contemp. 15 (2018) 441-466
In case when G is a weighted tree, the Hosoya polynomial was expressed as a sum of edge contributions and a recursive formula for computing the Hosoya polynomial was given in [26].
In this section we show that the Hosoya polynomial can be similarly expressed as a sum of edge contributions on general graphs, and then provide a somewhat more elaborated expression that holds for cactus graphs.
Lemma 6.4. The modified Hosoya polynomial, defined by (3.5), is a sum of edge contributions
M(G,x) = E A(e) • Me(G, x),	(6.1)
e£E(G)
where Me(G, x) is given by
Me(G,x)= V n*(u,V,e) w(w)w(v)xd("'v).	(6.2)
—^ n* (u v)
P,' ,,

Here P* 3 e denotes a shortest path between u and v including e, n* (u, v) is the number of all shortest paths with endpoints u and v and n*(u, v, e) is the number of all shortest paths with endpoints a and b including edge e.
Proof. To see this, it is enough to sum up the contribution of each edge to M(G, x) in two different ways. Each pair of vertices u, v contributes d(u, v)w(u)w(v)xd("'v) to the modified Hosoya polynomial. This can be regarded as a contribution of the pair u, v or it can be divided into n* (u, v, e)/n* (u, v) path contributions, which can be further regarded as a sum of edge contributions along the path. An edge contributes as many times as it appears on various shortest paths. Hence, one can sum up the lengths of all shortest paths, or, equivalently, sum up the contributions of all edges.	□
Let G be a cactus graph. Recall that each edge e of a cactus graph is on at most one cycle, in other words, either e is not on a cycle or there is a unique cycle C with e G C .On the other hand, a vertex in a cactus graph can lie on more than one cycle.
In case when the edge e = ab does not lie on a cycle, we can write our graph G as disjoint union of two graphs, denote them Ga and Gb, connected with edge e = ab (defined in Lemma 4.1), see Figure 1.
On the other side, when edge e with endpoints a and b lies on a cycle C, we can use notations from Lemma 5.1, see Figure 4: e is one of the edges named ajai+1 with a4 = a and ai+1 = b, Gai = Ga, Gai+1 = Gb for some i G {1, 2,..., n}. We can also say that Ga is the connected component of G - E(C) with a G G - E(C), where G - E(C) denotes the graph G without edges of the cycle C.
According to Lemma 4.1 and Lemma 5.1, we can derive the Hosoya polynomials Hi(G, x) and M(G, x) for a cactus graph G as sums of edge contributions.
Theorem 6.5. The modified Hosoya polynomial M(G, x) on a weighted cactus graph G is a sum of edge contributions
x
M(G,x)= E Ale)^ (/^ A. If « +
e=abEE(G)	K ' W	/ \o
e not on a cycle
T. Novak et al.: The Hosoya polynomial of double weighted graphs
459
LET S g( ( / ^ '*)( / -
e on a cycle
In case when e = ab is on a cycle C with girth L and vertices
b = bo, bi, 62, ..., 6m, a_K, a_K—1, .. ., ai, ao = a,
,, ^ fl, d(ai ,bj ) = L/2 we define N, = <
10, otherwise.
Proof. As every edge e of a cactus graph G does not lie on a cycle or there is unique cycle including e, we can discuss separately the two cases.
Case 1: The edge e with endpoints a and b does not lie on a cycle. Then G = Ga U {e} U Gb
n*(u,v,e) n* (u,v)
(see Figure 1) and, obviously, " *(u,iv,',e) = 1 for all u G Ga and all v G Gb.
Using the definition (3.6)
H0(G0, x) • HT&(G&, x) = w(a)w(b)	w(u)w(v)x

«ev (Ga) vev (Gb)
and
iH0(G0,x) • iH6(G6,x) • xA(e) ^	n d(« v)
w w	«ev (Ga)
vev (Gb)
since d(u, a) + A(e) + d(b, v) = d(u, v). So, the contribution (6.2) of the edge e in Case 1 is equal to
, Ho(Go,x) • iH5(G5,x) • xA(e) Me(G,x) = --^
w(a)w(b)
\o
(a)w(b)
T dt ———dt
xA(eW /"Mo(Go,tK	M6(G6,i)
Case 2: The edge e with endpoints a and b lies on a cycle C with girth L. Let A = {a = a0, ai, a2,..., aK} be the set of vertices of C that are closer to a than to b, i.e.
d(a, aj) < d(b, a4). B = {b = b0, bi, b2,..., bM} the set of vertices of C that are closer to b than to a, i.e. d(b, bj) < d(a, bj).
Clearly, for a pair of vertices aj G A, bj G B the edge e lies on the unique shortest path between them exactly when d(a, b) = d(a, aj) + A(e) + d(b, bj) < L/2. Furthermore, e is on one of the two shortest paths exactly when d(a, b) = d(a, aj) + A(e) + d(b, bj) = L/2 and is not on a shortest path between aj and bj when d(a, b) < d(a, aj) + A(e) + d(b, bj). Denote
HH0. (G0i, x)= w(w)w(aj)xd(" '0i) = w(a,) ^ w(u)x
"eG«.	"eG«.	i = 0,1,...,K
d(u , 0i) i
460
Ars Math. Contemp. 15 (2018) 441-466
Hb3 (Gbj ,x)=^2, w (bj)w(v)xd(bj'v) = w(bj) J2 w(v)xd(bj'v)
veGb	veGb
j = 0,1,...,M. Since
Hiai (Gai ,x) • Hibj (Gbj ,x) • xd(aib)
w(u)w(v)x
d(u,v)
w(ai)w(bj) v ' v j	uev(Gai)
vev (Gbj)
the contribution (6.2) of the edge e in Case 2 is equal to
KM ( 1 \Nij Hi a (Ga■ ,x) • lib-(Gb. ,x) • xd(ai'bj) e( , ) hh^-2)	w(ai)w(bj)
=t t (2 r ¡¿j a ™ Ait -
i=0 j=0 Vq
where
N |1, d(ai,bj ) = L/2 lj 10, otherwise.
As we mentioned earlier, the case nn*uuv) = 2 appears only when u e Gai, v e Gbj and
o,i and bj are opposite vertices of a cycle C, such that d(ai, bj) = L/2. In all other cases
n'iu'v'e) =1. □ n* (u,v)
7 Linear algorithm
In this section we give some details of the algorithm for computing Hosoya polynomial of a weighted cactus graph that is based on results provided in previous sections. Before writing the algorithm outline we recall the skeleton structure of a cactus graph and the depth first search algorithm. The algorithm and analysis of its time complexity are given in Subsection 7.2. The section is concluded with an example.
7.1 The structure of cactus graph and DFS algorithm
In the skeleton structure (elaborated for example in [2]) that corresponds to every cactus graph G = (V(G), E(G)), the vertices are of three types:
•	C-vertex is a vertex on a cycle of degree 2,
•	G-vertex is a vertex not included in any cycle,
•	H-vertex or a hinge is a vertex which is included in at least one cycle and is of degree > 3.
The depth first search (DFS) algorithm is a well known method for exploring graphs. It can be used for recognizing cactus graphs providing the data structure (see [17,21,22,23]). Let Gr be a rooted cactus graph with a root r. After running the DFS algorithm, the vertices of Gr are DFS ordered. The order is given by the order in which DFS visits the vertices.
T. Novak et al.: The Hosoya polynomial of double weighted graphs
461
(Note that the DFS order of a graph is not unique as we can use any vertex as the starting vertex (the root) and can visit the neighbors of a vertex in any order. However, here we can assume that the DFS order is given and is fixed.)
For any vertex v e V(G) we denote by DFN(v) the position of v in the DFS order and we set DFN(r) = 0. DFN is called the depth first number. Following [22], it is useful to store the information recorded during the DFS run in four arrays, called the DFS (cactus) data structure:
•	FATHER(v) is the unique predecessor (father) of the vertex v in the rooted tree, constructed with the DFS.
•	ROOT(v) is the root vertex of the cycle containing v i.e. the first vertex of the cycle (containing v) in the DFS order. If v does not lie on a cycle, then ROOT(v) = v by definition. We set ROOT(r) = r. (In any DFS order, if DFN(w) < DFN(v) and w is the root of the cycle containing v and v is the root of another cycle (it is a hinge), then ROOT(v) = w.)
•	For vertices on a cycle (i.e. ROOT(v) = v), orientation of the cycle is given by ORIEN(v) = z, where z is the son of ROOT(v) that is visited on the cycle first. If
ROOT(v) = v, then ORIEN(v) = v.
•	IND(v) := |{u | FATHER(u) = v}| is the number of sons of v in the DFS tree.
We omit detailed description of DFS algorithm here, as it is well known, see for example [21]. The pseudocode of the DFS algorithm is also written in [17]. Some properties of the DFS ordered vertices of cactus and the relationship between the definitions of C, G, H-vertices in a rooted cactus Gr and arrays in the DFS table is described in [17].
In the rest of the paper the following notations are used. For a given cactus graph G and a vertex v e V(G) let Gv be the rooted induced subgraph of G with the root v. The set of vertices of Gv is the set V(Gv) = {w e V(G) | DFN(w) > DFN(v)}. Let u = FATHER(v) and let the edge uv not be an edge of a cycle of G (i.e. ROOT(v) = v). The graph Gu is the induced rooted subgraph of G with the root u. The set of vertices of Gu is the set V(Gu) = {w e V(G) | DFN(u) < DFN(w) < DFN(v)}. The sketch of rooted graphs Gv, Gu and Gu is shown in Figure 8.
Figure 8: A rooted graph G,
462
Ars Math. Contemp. 15 (2018) 441-466
7.2 The algorithm
The linear algorithm consists of three steps. First, the representation of a given weighted cactus is found, then, in Step 2 the initialization for the recursive algorithm is done and in the third step, the Hosoya polynomials of certain rooted subgraphs are computed recursively that finally give the Hosoya polynomial of the whole graph. More precisely, in Step 3 we traverse the DFS tree of the cactus in the reversed DFS order and for each vertex v compute Hv (Gv ,x) and H(Gv ,x). The algorithm continues until the last vertex in the back DFS order is considered, which is the root r of the cactus. The result follows from the fact that H(G, x) = H(Gr, x).
We now give more details of each step.
Step 1: Cactus recognition
Using a DFS algorithm on the rooted cactus G (any vertex chosen for a root) the data structure of cactus graph can be derived, including arrays DFN(v), FATHER(v), ROOT(v), ORIEN(v) and IND(v).
Step 2: Initialization
For every vertex v we set
Hv (Gv ,x) = Hv ({v},x) = w(v)2 and H(Gv ,x) = H({v},x) = 0.
Step 3: Computation of polynomials H
Start with v, the last vertex in the DFS order. Let u = FATHER(v). While v = u (i.e. v = u is not the root of G) do (3a) or (3b):
(3a) If the edge e = uv is not an edge of a cycle of G (i.e. ROOT(v) = v):
•	If DFN(u) = DFN(v) - 1 (i.e. DFN(u) < DFN(v) - 1), there exists rooted subgraph Gu (see Figure 8). The algorithm calls itself recursively for the subgraph Gu, the rooted subcactus with root u and vertices in DFS table with DFN(u),..., DFN(v) - 1. We obtain H(Gu,x) = H(Gu,x) and
Hu(Gu,x) = Hu(Gu,x).
•	After the recursion or when u and v are the sequential vertices in the DFS order, polynomials Hu (Gu, x) and H(Gu, x) are calculated according to Lemma 4.1:
H(Gu,x) = H(Gu,x) + H(GV,x) + w(u}w(v) Hu(Gu,x)Hv(Gv,x)xx(uv) Hu(Gu, x) = Hu(Gu, x) + WuHv (Gv,x)xx(uv).
•	v = u and u = FATHER(v).
(3b) If the edge e = uv lies on a cycle C (i.e. r = ROOT(v) = v):
•	We have to read and remember all cycle's vertices. Denote them by a\,a2,..., an where ai = v, an-1 = ORIEN(v) and an = r = ROOT(v).
•	If DFN(aj) < DFN(aj-i) - 1, denote by Kaj the rooted subcacti on vertices with DFN: DFN(aj) < DFN < DFN(aj-lL) for j = 2,3,...,n - 1. Re-
T. Novak et al.: The Hosoya polynomial of double weighted graphs
463
cursively calculate polynomials HT(Kaj, x) and iHaj (Ka,, x) and repair polynomials HT(Gaj, x) and iHaj (Ga,, x) following Lemma 4.4:
HT(Gaj , x) = HT(Gaj , x) + i/(Kaj, x) +
+ wj (HHaj (Gaj ,x) - w(aj )2)(iHa3 (Ka,, x) - w(a,j )2) Haj (Ga, , x) = Ha, (Ga, , x) + Fa, (Ka, , x) - w(a,j )2 .
•	According to the discussion in Section 5 we calculate HTr (Gr, x) and HT(Gr, x) using details H^G^., x) and HT^. (Ga,, x), j = 1, 2,..., n.
•	u is the vertex with DFN(u) = DFN(ORIEN(v)) - 1.
•	v = u and u = FATHER(v).
We conclude the subsection summarizing the time complexity. Step 1: It is well-known that traversing the graph with DFS algorithm and computing arrays DFN(v), FATHER(v), ROOT(v), ORIEN(v) and IND(v) can be done within O(m) time. Obviously, Step 2 can be computed in O(m) time. In Step 3, existence of implementation that uses O(m) additions and multiplications of polynomials follows from Lemmata 4.1,4.4, 5.1, and Theorem 5.7. Hence we can conclude that the algorithm runs in linear time.
Theorem 7.1. The algorithm for the Hosoya polynomial on a weighted cactus graph (given in Subsection 7.2) correctly calculates the polynomial, in linear time in the model where the addition and multiplication ofpolynomials are atomic operations.
7.3 Example
Example 7.2. Let G be a cactus graph in Figure 9 (high) with representing DFS tree (one of possibilities) in Figure 9 (low) and its DFS structure in Table 1.
Table 1: The DFS structure of graph G.
v	DFN(v)	FATHER(v)	ROOT(v)	ORIEN(v)	IND(v)
Vl	0	Vl	Vl	V2	2
V2	1	Vl	Vl	V2	3
V3	2	V2	V3	V3	0
V4	3	V2	V4	V4	0
V5	4	V2	Vl	V2	2
V6	5	V5	V6	V6	1
V7	6	V6	V7	V7	0
V8	7	V5	Vl	V2	1
Vg	8	V8	Vg	Vg	0
Starting from the initialization (Step 2) and following the algorithm (Step 3), we obtain
• v = vg, u = vg: Gv9 = {vg}, Gv8 = {vg, vg} U vgvg,
-	step 2: iiV9 (Gv9, x) = 1, Hf(GV9, x) = 0,
-	step (3a): HHV8 (Gv8, x) = x +1, HH(Gv8, x) = x.
464	Ars Math. Contemp. 15 (2018) 441-466
Figure 9: A weighted cactus graph G (high) and its DFS tree (low).
• v = v8, u = V5: V5V8 is on cycle with ai = vs, 02 = V5, 03 = V2, 04 = vi,
-	step (3b): Kv6 = {v5,v6,vr}U V5V6 U V6V7, Kv2 = {v2,v3,v4}U V2V3 U V2V4,
-	recursively:
H (KV6, x) = 2x3 + 2x2 + x, HV6 (KV6, x) = 2x3 + 2x2 + 4, HH(KV2, x) = 2x3 + 4x2 + 2x, HV2 (KV2, x) = 4x2 + 2x + 4,
-	from Lemma 4.4:
{V5, V6, V7, Vs, V9} U V5V6 U V6V7 U V5V8 U V8V9, {V2, V3, V4, V5, V6, V7, vs, V9} U V2V3 U V2V4 U V2V5 U V5V6 U
U V6V7 U V5V8 U V8V9, x6 + 2x5 + x4 + 4x3 + 4x2 + 2x, 4x3 + 4x2 + 4,
5x6 + 8x5 + 7x4 + 14x3 + 14x2 + 8x, 4x4 + 4x3 + 4x2 + 4x + 4,
c —
GV6 = GV2 =
H(Gv6 ,x) =
H^V6 (GV6 , x)
H(Gv2, x) =
V2 (GV2 , x)
T. Novak et al.: The Hosoya polynomial of double weighted graphs
465
- according to discussion in Section 5 we calculate (GV1 = G)
H(GV1, x) = 6x6 + 9x5 + 9x4 + 17x3 + 13x2 + 9x, HV1 (GV1 ,x) = x6 + x5 + 2x4 + 3x3 + 3x2 + x + 1,
• v = v1,u = v1: end of the algorithm.
Finally, the Hosoya polynomial of graph G equals
H(G, x) = H(GV1, x) = 6x6 + 9x5 + 9x4 + 17x3 + 13x2 + 9x.
References
[1]	F. M. Briickler, T. Doslic, A. Graovac and I. Gutman, On a class of distance-based molecular structure descriptors, Chem. Phys. Lett. 503 (2011), 336-338, doi:10.1016/j.cplett.2011.01. 033.
[2]	R. E. Burkard and J. Krarup, A linear algorithm for the pos/neg-weighted 1-median problem on a cactus, Computing 60 (1998), 193-215, doi:10.1007/bf02684332.
[3]	G. G. Cash, Relationship between the Hosoya polynomial and the hyper-Wiener index, Appl. Math. Lett. 15 (2002), 893-895, doi:10.1016/s0893-9659(02)00059-9.
[4]	E. Deutsch and S. Klavzar, Computing the Hosoya polynomial of graphs from primary subgraphs, MATCH Commun. Math. Comput. Chem. 70 (2013), 627-644, http://match.pmf.kg.ac.rs/electronic_versions/Match7 0/n2/ match70n2_627-644.pdf.
[5]	T. Doslic, Vertex-weighted Wiener polynomials for composite graphs, Ars Math. Contemp. 1 (2008), 66-80, doi:10.26493/1855-3974.15.895.
[6]	B. Elenbogen and J. F. Fink, Distance distributions for graphs modeling computer networks, Discrete Appl. Math 155 (2007), 2612-2624, doi:10.1016/j.dam.2007.07.020.
[7]	M. Eliasi and A. Iranmanesh, Hosoya polynomial of hierarchical product of graphs, MATCH Commun. Math. Comput. Chem. 69 (2013), 111-119, http://match.pmf.kg.ac.rs/ electronic_versions/Match6 9/n1/match69n1_111-119.pdf.
[8]	J. Galtier, I. Pesek, K. Prnaver and J. Zerovnik, Oriented networks design problem, J. Inf. Sci. Eng. 26 (2010), 1231-1242, http://www.iis.sinica.edu.tw/page/jise/2010/ 201007_05.html.
[9]	I. Gutman, Selected properties of the Schultz molecular topological index, J. Chem. Inf. Comput. Sci. 34 (1994), 1087-1089, doi:10.1021/ci00021a009.
[10]	I. Gutman and B. Furtula (eds.), Distance in Molecular Graphs - Theory, volume 12 of Mathematical Chemistry Monographs, University of Kragujevac, Kragujevac, 2012, http: //match.pmf.kg.ac.rs/mcm12.html.
[11]	I. Gutman, S. KlavZar, M. Petkovsek and P. Zigert, On Hosoya polynomials of benzenoid graphs, MATCH Commun. Math. Comput. Chem. 43 (2001), 49-66, http://match.pmf. kg.ac.rs/electronic_versions/Match43/match4 3_4 9-66.pdf.
[12]	H. Hosoya, On some counting polynomials in chemistry, Discrete Appl. Math. 19 (1988), 239257, doi:10.1016/0166-218x(88)90017-0.
[13]	S. Klavzsar and I. Gutman, Wiener number of vertex-weighted graphs and a chemical application, Discrete Appl. Math. 80 (1997), 73-81, doi:10.1016/s0166-218x(97)00070-x.
466
Ars Math. Contemp. 15 (2018) 441-466
[14]	S. Klavzar and M. Mollard, Wiener index and Hosoya polynomial of Fibonacci and Lucas cubes, MATCH Commun. Math. Comput. Chem. 68 (2012), 311-324, http://match.pmf. kg.ac.rs/electronic_versions/Match68/n1/match68n1_311-32 4.pdf.
[15]	M. Knor, R. Skrekovski and A. Tepeh, Mathematical aspects of Wiener index, Ars Math. Con-temp. 11 (2016), 327-352, doi:10.26493/1855-3974.795.ebf.
[16]	X. Lin, S.-J. Xu and Y.-N. Yeh, Hosoya polynomials of circumcoronene series, MATCH Commun. Math. Comput. Chem. 69 (2013), 755-763, http://match.pmf.kg.ac.rs/ electronic_versions/Match6 9/n3/match69n3_755-7 63.pdf.
[17]	T. Novak and J. Zerovnik, Weighted domination number of cactus graphs, Int. J. Appl. Math. 29 (2016), 401-423, doi:10.12732/ijam.v29i4.1.
[18]	I. Pesek, M. Rotovnik, D. Vukicevic and J. Zerovnik, Wiener number of directed graphs and its relation to the oriented network design problem, MATCH Commun. Math. Comput. Chem. 64 (2010), 727-742, http://match.pmf.kg.ac.rs/electronic_ versions/Match64/n3/match64n3_727-7 42.pdf.
[19]	T. Pisanski and J. Zerovnik, Edge-contributions of some topological indices and arboreality of molecular graphs, Ars Math. Contemp. 2 (2009), 49-58, doi:10.26493/1855-3974.68.51b.
[20]	B. E. Sagan, Y.-N. Yeh and P. Zhang, The Wiener polynomial of a graph, Int. J. Quantum Chem. 60 (1996), 959-969, doi:10.1002/(sici)1097-461x(1996)60:5(959::aid-qua2)3.0.co;2-w.
[21]	K. Thulasiraman and M. N. S. Swamy, Graphs: Theory and Algorithms, A Wiley-Interscience Publication, John Wiley & Sons, New York, 1992, doi:10.1002/9781118033104.
[22]	B. Zmazek and J. Zerovnik, Computing the weighted Wiener and Szeged number on weighted cactus graphs in linear time, Croat. Chem. Acta 76 (2003), 137-143, https://hrcak. srce.hr/103089.
[23]	B. Zmazek and J. Zerovnik, The obnoxious center problem on weighted cactus graphs, Discrete Appl. Math. 136 (2004), 377-386, doi:10.1016/s0166-218x(03)00452-9.
[24]	B. Zmazek and J. Zerovnik, Estimating the traffic on weighted cactus networks in linear time, in: 9th International Conference on Information Visualisation, IEEE Computer Society, Los Alamitos, 2005 pp. 536-541, doi:10.1109/iv.2005.48, held in London, UK, July 6-8, 2005.
[25]	B. Zmazek and J. Zerovnik, On generalization of the Hosoya-Wiener polynomial, MATCH Commun. Math. Comput. Chem. 55 (2006), 359-362, http://match.pmf.kg.ac.rs/ electronic_versions/Match55/n2/match55n2_35 9-3 62.pdf.
[26]	B. Zmazek and J. Zerovnik, The Hosoya-Wiener polynomial of weighted trees, Croat. Chem. Acta 80 (2007), 75-80, https://hrcak.srce.hr/12 82 7.