On the edge-Wiener index of the disjunctive product of simple graphs
The edge-Wiener index of a simple connected graph G is defined as the sum of distances between all pairs of edges of G where the distance between two edges in G is the distance between the corresponding vertices in the line graph of G. In this paper, we study the edge-Wiener index under the disjunct...
Gespeichert in:
| Datum: | 2020 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2020
|
| Schriftenreihe: | Algebra and Discrete Mathematics |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/188549 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | On the edge-Wiener index of the disjunctive product of simple graphs / M. Azari, A. Iranmanesh // Algebra and Discrete Mathematics. — 2020. — Vol. 30, № 1. — С. 1–14. — Бібліогр.: 24 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-188549 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1885492023-03-08T01:26:59Z On the edge-Wiener index of the disjunctive product of simple graphs Azari, M. Iranmanesh, A. The edge-Wiener index of a simple connected graph G is defined as the sum of distances between all pairs of edges of G where the distance between two edges in G is the distance between the corresponding vertices in the line graph of G. In this paper, we study the edge-Wiener index under the disjunctive product of graphs and apply our results to compute the edge-Wiener index for the disjunctive product of paths and cycles. 2020 Article On the edge-Wiener index of the disjunctive product of simple graphs / M. Azari, A. Iranmanesh // Algebra and Discrete Mathematics. — 2020. — Vol. 30, № 1. — С. 1–14. — Бібліогр.: 24 назв. — англ. 1726-3255 DOI:10.12958/adm242 2010 MSC: 05C76, 05C12, 05C38 http://dspace.nbuv.gov.ua/handle/123456789/188549 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
The edge-Wiener index of a simple connected graph G is defined as the sum of distances between all pairs of edges of G where the distance between two edges in G is the distance between the corresponding vertices in the line graph of G. In this paper, we study the edge-Wiener index under the disjunctive product of graphs and apply our results to compute the edge-Wiener index for the disjunctive product of paths and cycles. |
| format |
Article |
| author |
Azari, M. Iranmanesh, A. |
| spellingShingle |
Azari, M. Iranmanesh, A. On the edge-Wiener index of the disjunctive product of simple graphs Algebra and Discrete Mathematics |
| author_facet |
Azari, M. Iranmanesh, A. |
| author_sort |
Azari, M. |
| title |
On the edge-Wiener index of the disjunctive product of simple graphs |
| title_short |
On the edge-Wiener index of the disjunctive product of simple graphs |
| title_full |
On the edge-Wiener index of the disjunctive product of simple graphs |
| title_fullStr |
On the edge-Wiener index of the disjunctive product of simple graphs |
| title_full_unstemmed |
On the edge-Wiener index of the disjunctive product of simple graphs |
| title_sort |
on the edge-wiener index of the disjunctive product of simple graphs |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2020 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/188549 |
| citation_txt |
On the edge-Wiener index of the disjunctive product of simple graphs / M. Azari, A. Iranmanesh // Algebra and Discrete Mathematics. — 2020. — Vol. 30, № 1. — С. 1–14. — Бібліогр.: 24 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT azarim ontheedgewienerindexofthedisjunctiveproductofsimplegraphs AT iranmanesha ontheedgewienerindexofthedisjunctiveproductofsimplegraphs |
| first_indexed |
2025-07-16T10:39:12Z |
| last_indexed |
2025-07-16T10:39:12Z |
| _version_ |
1837799680101056512 |
| fulltext |
“adm-n3” — 2021/1/3 — 11:48 — page 1 — #7
© Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 30 (2020). Number 1, pp. 1–14
DOI:10.12958/adm242
On the edge-Wiener index of the disjunctive
product of simple graphs
M. Azari∗ and A. Iranmanesh
Communicated by D. Simson
Abstract. The edge-Wiener index of a simple connected
graph G is defined as the sum of distances between all pairs of edges
of G where the distance between two edges in G is the distance
between the corresponding vertices in the line graph of G. In this
paper, we study the edge-Wiener index under the disjunctive product
of graphs and apply our results to compute the edge-Wiener index
for the disjunctive product of paths and cycles.
Introduction
Throughout this paper, we consider connected finite graphs without
any loops or multiple edges. Let G be such a graph with vertex set V (G)
and edge set E(G). A topological index (also known as graph invariant) is
any function on a graph that does not depend on a labeling of its vertices.
Several hundreds of different invariants have been employed to date with
various degrees of success in QSAR/QSPR studies. We refer the reader to
[12] for review.
The oldest topological index is the one put forward in 1947 by Harold
Wiener [23] nowadays referred to as the Wiener index. Wiener used his
index for the calculation of the boiling points of alkanes. The Wiener
∗Corresponding author.
2010 MSC: 05C76, 05C12, 05C38.
Key words and phrases: distance in graphs, edge-Wiener index, disjunctive
product of graphs.
https://doi.org/10.12958/adm242
“adm-n3” — 2021/1/3 — 11:48 — page 2 — #8
2 Edge-Wiener index of the disjunctive product
index W (G) of a graph G is defined as the sum of distances between all
pairs of vertices of G,
W (G) =
∑
{u,v}⊆V (G)
d(u, v |G),
where d(u, v |G) denotes the distance between the vertices u and v of G
which is defined as the length of any shortest path in G connecting them.
We denote d(u, v |G) simply by d(u, v) when no ambiguity is present.
Details on the mathematical properties of the Wiener index and its appli-
cations in chemistry can be found in [8, 10,11,13–15].
Motivated by definition of the Wiener index, the edge-Wiener index
was introduced based on distance between all pairs of edges in a graph in
2009 [9, 19, 21]. The edge-Wiener index of a graph G is defined as
We(G) =
∑
{f,g}⊆E(G)
de(f, g |G),
where de(f, g |G) denotes the distance between the edges f and g of
G which is defined as the ordinary distance between the corresponding
vertices in the line graph L(G) of G. So, We(G) = W (L(G)). It has been
proved that [19], for each pair of edges f = uv and g = zt of G,
de(f, g |G) =
{
min{d(u, z), d(u, t), d(v, z), d(v, t)}+ 1 if f 6= g,
0 if f = g.
For details on the theory of the edge-Wiener index and its applications
see [2, 22,24] and specially the recent paper [18].
Many graphs are composed of simpler graphs via various graph opera-
tions also known as graph products. These composite graphs have more
complicated structures than their components. So, in general, computing
their topological invariants is more difficult than computing the topological
invariants of their components. So, it is important to understand how cer-
tain invariants of such composite graphs are related to the corresponding
invariants of their components. The edge-Wiener index of some graph
operations have been computed before [1, 3–7]. In this paper, we study
the behavior of the edge-Wiener index under the disjunctive product of
graphs and apply our results to compute the edge-Wiener index for the
disjunctive product of paths and cycles. We refer the reader to [17] for
details on the properties and applications of graph operations.
“adm-n3” — 2021/1/3 — 11:48 — page 3 — #9
M. Azari, A. Iranmanesh 3
1. Definitions and preliminaries
For a simple connected graph G, let NG(u) denote the open neighbor-
hood of a vertex u in G which is the set of all vertices of G adjacent with
u. The cardinality of NG(u) is called the degree of u in G and denoted
by dG(u). If there is no confusion, we simply use N(u) and d(u) instead
of NG(u) and dG(u), respectively. Let ∆(G) denote the number of all
triangles (3-cycles) in G and M1(G) denote the first Zagreb index of G
which is one the oldest topological indices introduced by Gutman and
Trinajstić [16] as follow.
M1(G) =
∑
u∈V (G)
d(u)2 =
∑
uv∈E(G)
(
d(u) + d(v)
)
. (1)
It is easy to check that,
∑
uv∈E(G)
|N(u) ∩N(v)| = 3∆(G) (2)
and
∑
u,v∈V (G)
|N(u) ∩N(v)| = M1(G). (3)
Using the inclusion–exclusion principle and then (1), (2), and (3), one can
easily get the following equations.
∑
uv∈E(G)
|N(u) ∪N(v)| = M1(G)− 3∆(G) (4)
and
∑
u,v∈V (G)
|N(u) ∪N(v)| = 4ne−M1(G), (5)
where n and e denote the order and size of the graph G, respectively.
Here, we introduce some useful notations which will be used throughout
the paper.
ν(G) =
∑
uv∈E(G)
|N(u) ∪N(v)|2 , (6)
ν∗(G) =
∑
u,v∈V (G)
|N(u) ∪N(v)|2 , (7)
“adm-n3” — 2021/1/3 — 11:48 — page 4 — #10
4 Edge-Wiener index of the disjunctive product
µ(G) =
∑
uv∈E(G)
∑
z∈V (G)\(N(u)∪N(v))
∣
∣N(z) \
(
N(u) ∪N(v)
)∣
∣ , (8)
and
µ∗(G) =
∑
u,v∈V (G)
∑
z∈V (G)\(N(u)∪N(v))
∣
∣N(z) \
(
N(u) ∪N(v)
)
∣
∣ . (9)
2. Results and discussion
Let G1 and G2 be two simple connected graphs. We denote by V (Gi)
and E(Gi), the vertex set and edge set of Gi, respectively, where i ∈ {1, 2}.
The disjunctive product G1 ∨ G2 of graphs G1 and G2 is a graph with
the vertex set V (G1) × V (G2) and two vertices (u1, u2) and (v1, v2) of
G1 ∨ G2 are adjacent if and only if u1 and v1 are adjacent in G1 or u2
and v2 are adjacent in G2. The disjunctive product of two graphs is also
known as their co-normal product or OR product. The distance between
the vertices u = (u1, u2) and v = (v1, v2) of G1 ∨G2 is given by
d(u, v|G1 ∨G2) =
0 if u1 = v1, u2 = v2,
1 if u1v1 ∈ E(G1) or u2v2 ∈ E(G2),
2 otherwise.
In this section, we compute the edge-Wiener index of the disjunctive
product of G1 and G2. Throughout the section, for notational convenience,
we let G = G1 ∨G2 be the disjunctive product of a pair of graphs G1 and
G2, and n1, e1, n2, e2 denote the order of G1, size of G1, order of G2, size
of G2, respectively.
At first, we consider three subsets of E(G) as follows.
E1 ={(u1, u2)(v1, v2) | u1v1 ∈ E(G1), u2, v2 ∈ V (G2)},
E2 ={(u1, u2)(v1, v2) | u2v2 ∈ E(G2), u1, v1 ∈ V (G1)},
E3 ={(u1, u2)(v1, v2) | u1v1 ∈ E(G1), u2v2 ∈ E(G2)}.
It is clear that, E(G) =
⋃3
i=1Ei and
|E(G)| = |E1|+ |E2| − 2 |E3| = e1n
2
2 + e2n
2
1 − 2e1e2. (10)
Since all distinct vertices of G are either at distance 1 or 2, so all distinct
edges of G are either at distance 1, 2, or 3. Therefore, we can partition
the set of all pairs of edges of G into three sets as follows.
A ={{f, g} | de(f, g |G) = 1},
“adm-n3” — 2021/1/3 — 11:48 — page 5 — #11
M. Azari, A. Iranmanesh 5
B ={{f, g} | de(f, g |G) = 2},
C ={{f, g} | de(f, g |G) = 3}.
In order to find the edge-Wiener index of G, we should compute the
cardinality of the above sets. It is clear that,
|A|+ |B|+ |C| =
(
|E(G)|
2
)
=
(
e1n
2
2 + e2n
2
1 − 2e1e2
2
)
. (11)
By (11), it is enough to find the cardinality of the sets A and C.
In the following proposition, we compute the cardinality of the set A.
Proposition 1. The cardinality of the set A is given by
|A| =
1
2
[
n2(n
2
2 − 4e2)M1(G1) + n1(n
2
1 − 4e1)M1(G2) (12)
+M1(G1)M1(G2) + 8n1n2e1e2 − 2(e1n
2
2 + e2n
2
1 − 2e1e2)
]
.
Proof. Clearly, A is the set of all pairs of adjacent edges of G. So
|A| =
∑
u∈V (G)
(
d(u)
2
)
=
1
2
∑
u∈V (G)
(
d(u)2 − d(u)
)
=
1
2
M1(G)− |E(G)| .
By Theorem 3 in [20], the first Zagreb index of the disjunctive product of
G1 and G2 is given by
M1(G) =n2(n
2
2 − 4e2)M1(G1) + n1(n
2
1 − 4e1)M1(G2)
+M1(G1)M1(G2) + 8n1n2e1e2.
Now using (10), we can get (12).
Now we start to find the cardinality of the set C. Suppose f =
(u1, u2)(v1, v2) is an arbitrary edge of G and let C(f) be the set of all
edges of G which are at distance 3 from f ,
C(f) = {g ∈ E(G) | de(f, g |G) = 3}.
In the following lemma, we compute the cardinality of the set C(f).
Lemma 1. For every arbitrary edge f = (u1, u2)(v1, v2) of G, the cardi-
nality of the set C(f) is given by
|C(f)| =
1
2
[
(
n2 − |N(u2) ∪N(v2)|
)2
(13)
“adm-n3” — 2021/1/3 — 11:48 — page 6 — #12
6 Edge-Wiener index of the disjunctive product
×
∑
z1∈V (G1)\(N(u1)∪N(v1))
∣
∣N(z1) \
(
N(u1) ∪N(v1)
)∣
∣
+
(
n1 − |N(u1) ∪N(v1)|
)2
×
∑
z2∈V (G2)\(N(u2)∪N(v2))
∣
∣N(z2) \
(
N(u2) ∪N(v2)
)
∣
∣
−
∑
z1∈V (G1)\(N(u1)∪N(v1))
∣
∣N(z1) \
(
N(u1) ∪N(v1)
)
∣
∣
×
∑
z2∈V (G2)\(N(u2)∪N(v2))
∣
∣N(z2) \
(
N(u2) ∪N(v2)
)
∣
∣
]
.
Proof. Let f = (u1, u2)(v1, v2) be an arbitrary edge of G and let g =
(z1, z2)(t1, t2) be an arbitrary element of C(f). By definition of the distance
de, we have
1 + min{d
(
(u1, u2), (z1, z2)
)
, d
(
(u1, u2), (t1, t2)
)
, d
(
(v1, v2), (z1, z2)
)
,
d
(
(v1, v2), (t1, t2)
)
} = de(f, g|G) = 3.
Hence,
min{d
(
(u1, u2), (z1, z2)
)
, d
(
(u1, u2), (t1, t2)
)
, d
(
(v1, v2), (z1, z2)
)
,
d
(
(v1, v2), (t1, t2)
)
} = 2.
Since all distinct vertices of G are either at distance 1 or 2, so
d
(
(u1, u2), (z1, z2)
)
= d
(
(u1, u2), (t1, t2)
)
= d
(
(v1, v2), (z1, z2)
)
= d
(
(v1, v2), (t1, t2)
)
= 2.
This implies that, zi and ti are adjacent neither to ui nor to vi in Gi,
where i ∈ {1, 2}. Consequently,
|C(f)| =
1
2
∑
z1∈V (G1)\(N(u1)∪N(v1))
∑
z2∈V (G2)\(N(u2)∪N(v2))
[
∣
∣N(z1) \
(
N(u1)
∪N(v1)
)
∣
∣
(
n2 − |N(u2) ∪N(v2)|
)
+
∣
∣N(z2) \
(
N(u2) ∪N(v2)
)
∣
∣
(
n1 − |N(u1) ∪N(v1)|
)
−
∣
∣N(z1) \
(
N(u1) ∪N(v1)
)∣
∣
∣
∣N(z2) \
(
N(u2) ∪N(v2)
)∣
∣
]
.
=
1
2
[
∑
z1∈V (G1)\(N(u1)∪N(v1))
∣
∣N(z1) \
(
N(u1) ∪N(v1)
)
∣
∣
“adm-n3” — 2021/1/3 — 11:48 — page 7 — #13
M. Azari, A. Iranmanesh 7
∑
z2∈V (G2)\(N(u2)∪N(v2))
(
n2 − |N(u2) ∪N(v2)|
)
+
∑
z2∈V (G2)\(N(u2)∪N(v2))
∣
∣N(z2) \
(
N(u2) ∪N(v2)
)∣
∣
∑
z1∈V (G1)\(N(u1)∪N(v1))
(
n1 − |N(u1) ∪N(v1)|
)
−
∑
z1∈V (G1)\(N(u1)∪N(v1))
∣
∣N(z1) \
(
N(u1) ∪N(v1)
)∣
∣
∑
z2∈V (G2)\(N(u2)∪N(v2))
∣
∣N(z2) \
(
N(u2) ∪N(v2)
)∣
∣
]
.
Now, (13) is obtained after simplifying the above expression.
Let f = (u1, u2)(v1, v2) be an edge of G. Then, (u1, v2)(v1, u2) is also
an edge of G. We denote the edge (u1, v2)(v1, u2) by f̄ .
Lemma 2. For every arbitrary edge f = (u1, u2)(v1, v2) of G,
∣
∣C(f̄)
∣
∣ =
|C(f)|.
Proof. The cardinality of C(f̄) can easily be obtained by changing the
role of the vertices u2 and v2 in (13). On the other hand, one can easily
check that changing the role of these two vertices does not influence the
result. So
∣
∣C(f̄)
∣
∣ = |C(f)|.
In the following proposition, we obtain the cardinality of the set C.
Proposition 2. The cardinality of the set C is given by
|C| =
1
4
[(
n2
2(n
2
2 − 10e2) + ν∗(G2)− 2ν(G2) (14)
+ 6n2
(
M1(G2)− 2∆(G2)
)
)
µ(G1)
+
(
n2
1(n
2
1 − 10e1) + ν∗(G1)− 2ν(G1)
+ 6n1
(
M1(G1)− 2∆(G1)
)
)
µ(G2)
+
(
n2
2e2 + ν(G2)− 2n2
(
M1(G2)− 3∆(G2)
)
)
µ∗(G1)
+
(
n2
1e1 + ν(G1)− 2n1
(
M1(G1)− 3∆(G1)
)
)
µ∗(G2)
− µ(G1)µ
∗(G2)− µ(G2)µ
∗(G1) + 2µ(G1)µ(G2)
]
.
“adm-n3” — 2021/1/3 — 11:48 — page 8 — #14
8 Edge-Wiener index of the disjunctive product
Proof. For every f ∈ E(G), there exist |C(f)| elements in C. Furthermore,
for every pair of edges f, g in G, g ∈ C(f) if and only if f ∈ C(g). Hence,
|C| =
1
2
∑
f∈E(G)
|C(f)| =
1
2
[
∑
f∈E1
|C(f)|+
∑
f∈E2
|C(f)|
−
∑
f∈E3
(
|C(f)|+
∣
∣C(f̄)
∣
∣
)
]
.
Using Lemma 2, we obtain
|C| =
1
2
[
∑
f∈E1
|C(f)|+
∑
f∈E2
|C(f)| − 2
∑
f∈E3
|C(f)|
]
. (15)
Now, we compute
∑
f∈Ei
|C(f)|, for every i ∈ {1, 2, 3}.
By definition of the set E1 and (13), we have
∑
f∈E1
|C(f)| =
1
2
∑
u1v1∈E(G1)
∑
u2,v2∈V (G2)
[
(
n2 − |N(u2) ∪N(v2)|
)2
∑
z1∈V (G1)\(N(u1)∪N(v1))
∣
∣N(z1) \
(
N(u1) ∪N(v1)
)
∣
∣
+
(
n1 − |N(u1) ∪N(v1)|
)2
∑
z2∈V (G2)\(N(u2)∪N(v2))
∣
∣N(z2) \
(
N(u2) ∪N(v2)
)
∣
∣
−
∑
z1∈V (G1)\(N(u1)∪N(v1))
∣
∣N(z1) \
(
N(u1) ∪N(v1)
)
∣
∣
∑
z2∈V (G2)\(N(u2)∪N(v2))
∣
∣N(z2) \
(
N(u2) ∪N(v2)
)
∣
∣
]
.
By simplifying the above expression, we obtain
∑
f∈E1
|C(f)| =
1
2
[
∑
u2,v2∈V (G2)
(
n2 − |N(u2) ∪N(v2)|
)2
∑
u1v1∈E(G1)
∑
z1∈V (G1)\(N(u1)∪N(v1))
∣
∣N(z1) \
(
N(u1) ∪N(v1)
)
∣
∣
+
∑
u1v1∈E(G1)
(
n1 − |N(u1) ∪N(v1)|
)2
∑
u2,v2∈V (G2)
∑
z2∈V (G2)\(N(u2)∪N(v2))
∣
∣N(z2) \
(
N(u2) ∪N(v2)
)
∣
∣
“adm-n3” — 2021/1/3 — 11:48 — page 9 — #15
M. Azari, A. Iranmanesh 9
−
∑
u1v1∈E(G1)
∑
z1∈V (G1)\(N(u1)∪N(v1))
∣
∣N(z1) \
(
N(u1) ∪N(v1)
)
∣
∣
∑
u2,v2∈V (G2)
∑
z2∈V (G2)\(N(u2)∪N(v2))
∣
∣N(z2) \
(
N(u2) ∪N(v2)
)
∣
∣
]
.
Now using (4)−(9), we obtain
∑
f∈E1
|C(f)| =
1
2
[(
n4
2 + ν∗(G2)− 2n2
(
4n2e2 −M1(G2)
)
)
µ(G1)
+
(
n2
1e1 + ν(G1)− 2n1
(
M1(G1)− 3∆(G1)
)
)
µ∗(G2)
− µ(G1)µ
∗(G2)
]
.
(16)
By definition of the set E2 and (13), we have
∑
f∈E2
|C(f)| =
1
2
∑
u2v2∈E(G2)
∑
u1,v1∈V (G1)
[
(
n2 − |N(u2) ∪N(v2)|
)2
∑
z1∈V (G1)\(N(u1)∪N(v1))
∣
∣N(z1) \
(
N(u1) ∪N(v1)
)
∣
∣
+
(
n1 − |N(u1) ∪N(v1)|
)2
∑
z2∈V (G2)\(N(u2)∪N(v2))
∣
∣N(z2) \
(
N(u2) ∪N(v2)
)
∣
∣
−
∑
z1∈V (G1)\(N(u1)∪N(v1))
∣
∣N(z1) \
(
N(u1) ∪N(v1)
)
∣
∣
∑
z2∈V (G2)\(N(u2)∪N(v2))
∣
∣N(z2) \
(
N(u2) ∪N(v2)
)
∣
∣
]
.
By symmetry, we obtain
∑
f∈E2
|C(f)| =
1
2
[(
n4
1 + ν∗(G1)− 2n1
(
4n1e1 −M1(G1)
)
)
µ(G2)
+
(
n2
2e2 + ν(G2)− 2n2
(
M1(G2)− 3∆(G2)
)
)
µ∗(G1)
− µ(G2)µ
∗(G1)
]
.
(17)
By definition of the set E3 and (13), we have
∑
f∈E3
|C(f)| =
1
2
∑
u1v1∈E(G1)
∑
u2v2∈E(G2)
[
(
n2 − |N(u2) ∪N(v2)|
)2
“adm-n3” — 2021/1/3 — 11:48 — page 10 — #16
10 Edge-Wiener index of the disjunctive product
∑
z1∈V (G1)\(N(u1)∪N(v1))
∣
∣N(z1) \
(
N(u1) ∪N(v1)
)∣
∣
+
(
n1 − |N(u1) ∪N(v1)|
)2
∑
z2∈V (G2)\(N(u2)∪N(v2))
∣
∣N(z2) \
(
N(u2) ∪N(v2)
)
∣
∣
−
∑
z1∈V (G1)\(N(u1)∪N(v1))
∣
∣N(z1) \
(
N(u1) ∪N(v1)
)
∣
∣
∑
z2∈V (G2)\(N(u2)∪N(v2))
∣
∣N(z2) \
(
N(u2) ∪N(v2)
)∣
∣
]
.
Using (4), (6), and (8), we obtain
∑
f∈E3
|C(f)| =
1
2
[(
n2
2e2 + ν(G2)− 2n2
(
M1(G2)− 3∆(G2)
)
)
µ(G1)
+
(
n2
1e1 + ν(G1)− 2n1
(
M1(G1)− 3∆(G1)
)
)
µ(G2)
− µ(G1)µ(G2)
]
.
(18)
Now by (15)−(18), we can get (14).
Now, we are ready to compute the edge-Wiener index of the disjunctive
product of G1 and G2.
Theorem 1. Assume that G1 and G2 are simple connected graphs, G1∨G2
is the disjunctive product of G1 and G2, and n1, e1, n2, e2 denote the
order of G1, size of G1, order of G2, size of G2, respectively. Under the
notation introduced earlier, the edge-Wiener index We(G1 ∨ G2) of the
disjunctive product G1 ∨G2 of G1 and G2 is given by
We(G1 ∨G2) =
1
4
[(
n2
2(n
2
2 − 10e2) + ν∗(G2)− 2ν(G2) (19)
+ 6n2
(
M1(G2)− 2∆(G2)
)
)
µ(G1)
+
(
n2
1(n
2
1 − 10e1) + ν∗(G1)− 2ν(G1)
+ 6n1
(
M1(G1)− 2∆(G1)
)
)
µ(G2)
+
(
n2
2e2 + ν(G2)− 2n2
(
M1(G2)− 3∆(G2)
)
)
µ∗(G1)
+
(
n2
1e1 + ν(G1)− 2n1
(
M1(G1)− 3∆(G1)
)
)
µ∗(G2)
“adm-n3” — 2021/1/3 — 11:48 — page 11 — #17
M. Azari, A. Iranmanesh 11
− µ(G1)µ
∗(G2)− µ(G2)µ
∗(G1) + 2µ(G1)µ(G2)
− 2n2(n
2
2 − 4e2)M1(G1)− 2n1(n
2
1 − 4e1)M1(G2)
− 2M1(G1)M1(G2) + 4
(
e1n
2
2 + e2n
2
1 − 2e1e2
)2
− 16n1n2e1e2
]
.
Proof. Let G = G1 ∨G2. By applying Propositions 1-2, Lemmas 1-2, and
definition of the edge-Wiener index We(G), we get
We(G) =
∑
{f,g}⊆E(G)
de(f, g |G) =
∑
{f,g}∈A∪B∪C
de(f, g |G)
=
∑
{f,g}∈A
de(f, g |G) +
∑
{f,g}∈B
de(f, g |G) +
∑
{f,g}∈C
de(f, g |G)
= |A|+ 2 |B|+ 3 |C| = 2(|A|+ |B|+ |C|)− |A|+ |C| .
Now, using (11), (12), and (14), we can get (19).
Let Pn and Cn denote the n−vertex path and cycle, respectively. It
can be verified by a direct calculation that, for every n > 2,
M1(Pn) = 4n− 6; ∆(Pn) = 0;
ν(Pn) =
{
4 if n = 2,
16n− 30 if n > 3;
ν∗(Pn) =
{
10 if n = 2,
2(8n2 − 27n+ 31) if n > 3;
µ(Pn) =
{
0 if n = 2,
2(n− 3)(n− 4) if n > 3;
µ∗(Pn) =
{
0 if n = 2,
2(n− 3)(n2 − 6n+ 10) if n > 3.
Also for every n > 3,
M1(Cn) = 4n;
∆(Cn) =
{
1 if n = 3,
0 if n > 4;
ν(Cn) =
{
27 if n = 3,
16n if n > 4;
ν∗(Cn) =
{
160 if n = 4,
2n(8n− 13) if n 6= 4;
“adm-n3” — 2021/1/3 — 11:48 — page 12 — #18
12 Edge-Wiener index of the disjunctive product
µ(Cn) =
{
0 if n 6 4,
2n(n− 5) if n > 5;
µ∗(Cn) =
{
0 if n 6 4,
2n(n− 4)2 if n > 5.
Now using (19), we easily arrive at:
Corollary 1. For every integers n > 2 and m > 3,
We(Pn ∨ Cm)
=
150 if n = 2, m = 3,
432 if n = 2, m = 4,
m(m3 + 3m2 +m− 9) if n = 2, m > 5,
1
2(18n
4 + 24n3 − 39n2 − 45n+ 72) if n > 3, m = 3,
8(2n4 + 7n3 − 2n2 − 30n+ 38) if n > 3, m = 4,
1
2m
[
n4(3m− 5)
+ 2n3(3m2 − 18m+ 44)
+ n2(3m3 − 42m2 + 280m− 722)
− n(11m3 − 152m2 + 1038m− 2524)
+ 2(7m3 − 103m2 + 683m− 1583)
]
if n > 3, m > 5.
Acknowledgments
The authors would like to thank the referee for insightful comments
and valuable suggestions. The partial support by the Center of Excellence
of Algebraic Hyper-structures and its Applications of Tarbiat Modares
University (CEAHA) is gratefully acknowledged by the second author.
References
[1] M. Azari and A. Iranmanesh, Computation of the edge Wiener indices of the sum
of graphs, Ars Combin., V. 100, 2011, pp. 113-128.
[2] M. Azari and A. Iranmanesh, Computing Wiener-like topological invariants for
some composite graphs and some nanotubes and nanotori, In: I. Gutman, (Ed.),
Topics in Chemical Graph Theory, Univ. Kragujevac, Kragujevac, 2014, pp. 69-90.
[3] M. Azari and A. Iranmanesh, The second edge-Wiener index of some composite
graphs, Miskolc Math. Notes, V. 15, N. 2, 2014, pp. 305-316.
[4] M. Azari and A. Iranmanesh, Edge-Wiener type invariants of splices and links of
graphs, Politehn. Univ. Bucharest Sci. Bull. Ser. A Appl. Math. Phys., V. 77, N. 3,
2015, pp. 143-154.
“adm-n3” — 2021/1/3 — 11:48 — page 13 — #19
M. Azari, A. Iranmanesh 13
[5] M. Azari and A. Iranmanesh, Clusters and various versions of Wiener-type invari-
ants, Kragujevac J. Math., V. 39, N. 2, 2015, pp. 155-171.
[6] M. Azari, A. Iranmanesh and A. Tehranian, Computation of the first edge Wiener
index of a composition of graphs, Studia Univ. Babes Bolyai Chem., V. 55, N. 4,
2010, pp. 183-196.
[7] M. Azari, A. Iranmanesh and A. Tehranian, A method for calculating an edge
version of the Wiener number of a graph operation, Util. Math., V. 87, 2012, pp.
151-164.
[8] F. Cataldo, O. Ori and A. Graovac, Wiener index of 1-pentagon fullerenic infinite
lattice, Int. J. Chem. Model., V. 2, , 2010, pp. 165-180.
[9] P. Dankelman, I. Gutman, S. Mukwembi and H. C. Swart, The edge Wiener index
of a graph, Discrete Math., V. 309, 2009, pp. 3452-3457.
[10] M. R. Darafsheh and M. H. Khalifeh, Calculation of the Wiener, Szeged, and PI
indices of a certain nanostar dendrimer, Ars Combin., V. 100, 2011, pp. 289-298.
[11] M. V. Diudea, Wiener index of dendrimers, MATCH Commun. Math. Comput.
Chem., V. 32, 1995, pp. 71-83.
[12] M. V. Diudea, QSPR/QSAR Studies by Molecular Descriptors, NOVA, New York,
2001.
[13] T. Došlić, Splices, links and their degree-weighted Wiener polynomials, Graph
Theory Notes N. Y., V. 48, 2005, pp. 47–55.
[14] T. Došlić, Vertex-weighted Wiener polynomials for composite graphs, Ars Math.
Contemp., V. 1, N. 1, 2008, pp. 66-80.
[15] A. Graovac and T. Pisanski, On the Wiener index of a graph, J. Math. Chem., V.
8, 1991, pp. 53-62.
[16] I. Gutman and N. Trinajstić, Graph theory and molecular orbitals, Total π-electron
energy of alternant hydrocarbons, Chem. Phys. Lett., V. 17, 1972, pp. 535-538.
[17] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition, John Wiley
& Sons, New York, 2000.
[18] A. Iranmanesh and M. Azari, Edge-Wiener descriptors in chemical graph theory:
A survey, Curr. Org. Chem., V. 19, N. 3, 2015, pp. 219-239.
[19] A. Iranmanesh, I. Gutman, O. Khormali and A. Mahmiani, The edge versions
of the Wiener index, MATCH Commun. Math. Comput. Chem., V. 61, 2009, pp.
663-672.
[20] M. H. Khalifeh, H. Yousefi-Azari and A. R. Ashrafi, The first and second Zagreb
indices of some graph operations, Discrete Appl. Math., V. 157, 2009, pp. 804–811.
[21] M. H. Khalifeh, H. Yousefi-Azari, A. R. Ashrafi and S. G. Wagner, Some new
results on distance-based graph invariants, European J. Combin., V. 30, 2009, pp.
1149-1163.
[22] M. J. Nadjafi-Arani, H. Khodashenas and A. R. Ashrafi, Relationship between
edge Szeged and edge Wiener indices of graphs, Glas. Mat. Ser. III, V. 47, 2012, pp.
21-29.
[23] H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc.,
V. 69, N. 1, 1947, pp. 17–20.
“adm-n3” — 2021/1/3 — 11:48 — page 14 — #20
14 Edge-Wiener index of the disjunctive product
[24] H. Yousefi-Azari, M. H. Khalifeh and A. R. Ashrafi, Calculating the edge Wiener
and edge Szeged indices of graphs, J. Comput. Appl. Math., V. 235, N. 16, 2011,
pp. 4866-4870.
Contact information
Mahdieh Azari Department of Mathematics, Kazerun Branch,
Islamic Azad University, P. O. Box: 73135-168,
Kazerun, Iran
E-Mail(s): azari@kau.ac.ir
Ali Iranmanesh Department of Pure Mathematics, Faculty of
Mathematical Sciences, Tarbiat Modares
University, P. O. Box: 14115-137, Tehran, Iran
E-Mail(s): iranmanesh@modares.ac.ir
Received by the editors: 27.06.2016
and in final form 27.09.2017.
mailto:azari@kau.ac.ir
mailto:iranmanesh@modares.ac.ir
M. Azari, A. Iranmanesh
|