MULTIPLICATIVELY WEIGHTED HARARY INDICES OF GRAPH OPERATIONS

Journal of Applied Mathematics & Informatics.
2015.
Jan,
33(1_2):
89-100

- Received : August 27, 2013
- Accepted : August 06, 2014
- Published : January 30, 2015

Download

PDF

e-PUB

PubReader

PPT

Export by style

Share

Article

Metrics

Cited by

TagCloud

In this paper, we present exact formulae for the multiplica-tively weighted Harary indices of join, tensor product and strong product of graphs in terms of other graph invariants including the Harary index, Zagreb indices and Zagreb coindices. Finally, We apply our result to com-pute the multiplicatively weighted Harary indices of fan graph, wheel graph and closed fence graph.
AMS Mathematics Subject Classification : 05C12, 05C76.
u, v
∈
V
(
G
), the distance between
u
and
v
in
G
, denoted by
d_{G}
(
u, v
), is the length of a shortest (
u, v
)-path in
G
and let
d_{G}
(
v
) be the degree of a vertex
v
∈
V
(
G
). For two simple graphs
G
and
H
their
tensor product
, denoted by
G
×
H
, has vertex set
V
(
G
) ×
V
(
H
) in which (
g
_{1}
,
h
_{1}
) and (
g
_{2}
,
h
_{2}
) are adjacent whenever
g
_{1}
g
_{2}
is an edge in
G
and
h
_{1}
h
_{2}
is an edge in
H
. Note that if
G
and
H
are connected graphs, then
G
×
H
is connected only if at least one of the graph is nonbipartite. The
strong product
of graphs
G
and
H
, denoted by
G
⊠
H
, is the graph with vertex set
V
(
G
) ×
V
(
H
) = {(
u, v
) :
u
∈
V
(
G
),
v
∈
V
(
H
)} and (
u, x
)(
v, y
) is an edge whenever (
i
)
u
=
v
and
xy
∈
E
(
H
), or (
ii
)
uv
∈
E
(
G
) and
x
=
y
, or (
iii
)
uv
∈
E
(
G
) and
xy
∈
E
(
H
), see
Fig.1
.
Tensor and strong product of C _{3} and P _{3}
The
join G
+
H
of graphs
G
and
H
is obtained from the disjoint union of the graphs
G
and
H
, where each vertex of
G
is adjacent to each vertex of
H
.
A
topological index
of a graph is a real number related to the graph; it does not depend on labeling or pictorial representation of a graph. In theoretical chemistry, molecular structure descriptors (also called topological indices) are used for modeling physicochemical, pharmacologic, toxicologic, biological and other properties of chemical compounds
[11]
. There exist several types of such indices, especially those based on vertex and edge distances. One of the most intensively studied topological indices is the Wiener index; for other related topological indices see
[31]
.
Let
G
be a connected graph. Then
Wiener index
of
G
is defined as
with the summation going over all pairs of distinct vertices of
G
. Similarly, the
Harary index
of
G
is defined as
The Harary index of a graph
G
has been introduced independently by Plavsic et al.
[20]
and by Ivanciuc et al.
[16]
in 1993. Its applications and mathematical properties are well studied in [?,
32
,
19]
. Zhou et al.
[33]
have obtained the lower and upper bounds of the Harary index of a connected graph. Very recently, Xu et al.
[28]
have obtained lower and upper bounds for the Harary index of a connected graph in relation to
χ
(
G
), chromatic number of
G
and
ω
(
G
), clique number of
G
. and characterized the extremal graphs that attain the lower and upper bounds of Harary index. Various topological indices on tensor product, Cartesian product and strong product have been studied various authors, see
[2
,
29
,
30
,
4
,
21
,
22
,
23
,
17
,
13]
.
Dobrynin and Kochetova
[5]
and Gutman
[12]
independently proposed a vertex-degree-weighted version of Wiener index called degree distance or Schultz molecular topological index, which is defined for a connected graph
G
as
where
d_{G}
(
u
) is the degree of the vertex
u
in
G
. Note that the degree distance is a degree-weight version of the Wiener index. Hua and Zhang
[14]
introduced a new graph invariant named reciprocal degree distance, which can be seen as a degree-weight version of Harary index, that is,
Similarly, the modified Schultz molecular topological index or Gutman index is defined as
In Su et.al.
[26]
introduce the multiplicatively weighted Harary indices or reciprocal product-degree distance of graphs, which can be seen as a product -degree-weight version of Harray index
Hua and Zhang
[14]
have obtained lower and upper bounds for the reciprocal degree distance of graph in terms of other graph invariants including the degree distance, Harary index, the first Zagreb index, the first Zagreb coindex, pendent vertices, independence number, chromatic number and vertex and edgeconnectivity. Pattabiraman and Vijayaragavan
[24
,
25]
have obtained the exact expression for the reciprocal degree distance of join, tensor, strong and wreath product of graphs.
The
first Zagreb index
and
second Zagerb index
are defined as
In fact, one can rewrite the first Zagreb index as
Similarly, the
first Zagreb coindex
and
second Zagerb coindex
are defined as
The Zagreb indices are found to have appilications in QSPR and QSAR studies as well, see
[6]
. For the survey on theory and application of Zagreb indices see
[10]
. Feng et al.
[9]
have given a sharp bounds for the Zagreb indices of graphs with a given matching number. Khalifeh et al.
[18]
have obtained the Zagreb indices of the Cartesian product, composition, join, disjunction and symmetric difference of graphs. Ashrafi et al.
[3]
determined the extremal values of Zagreb coindices over some special class of graphs. Hua and Zhang
[15]
have given some relations between Zagreb coindices and some other topolodical indices. Ashrafi et al.
[1]
have obtained the Zagreb indices of the Cartesian product, composition, join, disjunction and symmetric difference of graphs.
A path, cycle and complete graph on
n
vertices are denoted by
P_{n}
,
C_{n}
and
K_{n}
, respectively. We call
C
_{3}
a triangle. In this paper, we present exact formulae for the multiplicatively weighted Harary indices of join, tensor product and strong product of graphs in terms of other graph invariants including the Harary index, Zagreb indices and Zagreb coindices. Finally, We apply our result to compute the multiplicatively weighted Harary indices of fan graph, wheel graph and closed fence graph.
Theorem 2.1.
Let G
_{1}
and G
_{2}
be graphs with n and m vertices p and q edges, respectively. Then
Proof
. Set
V
(
G
_{1}
) = {
u
_{1}
,
u
_{2}
, . . . ,
u_{n}
} and
V
(
G
_{2}
) = {
v
_{1}
,
v
_{2}
, . . . ,
v_{m}
}. By definition of the join of two graphs, one can see that,
Therefore,
Using Theorem 2.1, we have the following corollaries.
Corollary 2.2.
Let G be graph on n vertices and p edges. Then
Let
K_{n,m}
be the bipartite graph with two partitions having
n
and
m
vertices. Note that
Corollary 2.3.
One can observe that
M
_{1}
(
C_{n}
) = 4
n
,
n
≥ 3,
M
_{1}
(
P
_{1}
) = 0,
M
_{1}
(
P_{n}
) = 4
n
− 6,
n
> 1 and
M
_{1}
(
K_{n}
) =
n
(
n
− 1)
^{2}
. Similarly,
By direct calculations we obtain the second Zagreb indices and coindices of
P_{n}
and
C_{n}
.
Using Corollary 2.2, we compute the formulae for reciprocal degree distance of star, fan and wheel graphs,
see
Fig.2
.
Fan graph and wheel graph
Example 1.
G
×
K_{r}
.
The proof of the following lemma follows easily from the properties and structure of
G
×
K_{r}
. The lemma is used in the proof of the main theorem of this section.
Lemma 3.1.
Let G be a connected graph on n
≥ 2
vertices. For any pair of vertices x_{ij}
,
x_{kp}
∈
V
(
G
×
K_{r}
),
r
≥ 3,
i, k
∈ {1, 2, . . . ,
n
}
j, p
∈ {1, 2, . . . ,
r
}.
Then
(
i
)
If u_{i}u_{k}
∈
E
(
G
),
then
(
ii
)
If u_{i}u_{k}
≠
E
(
G
),
then d
_{G×Kr}
(
x_{ij}
,
x_{kp}
) =
d_{G}
(
u_{i}, u_{k}
).
(
iii
)
d
_{G×Kr}
(
x_{ij}
,
x_{ip}
) = 2.
Proof
. Let
V
(
G
) = {
u
_{1}
,
u
_{2}
, . . . ,
u_{n}
} and
V
(
K_{r}
) = {
v
_{1}
,
v
_{2}
, . . . ,
v_{r}
} . Let
x_{ij}
denote the vertex (
u_{i}, v_{j}
) of
G
×
K_{r}
. We only prove the case when
u_{i}u_{k}
∉
E
(
G
),
i
≠
k
and
j
=
p
. The proofs for other cases are similar.
We may assume
j
= 1. Let
P
=
u_{i}
u_{s}
_{1}
u_{s}
_{2}
. . .
u_{sp}
u_{k}
be the shortest path of ength
p
+ 1 between
u_{i}
and
u_{k}
in
G
. From
P
we have a (
x_{i}
_{1}
,
x_{k}
_{1}
)-path
P
_{1}
=
x_{i}
_{1}
x_{s}
_{1}
_{2}
. . .
x
_{sp}
_{-1}
_{2}
x
_{sp}
_{3}
x_{k}
_{1}
if the length of
P
is odd, and
P
_{1}
=
x_{i}
_{1}
x_{s}
_{1}
_{2}
. . .
x
_{sp}
_{-1}
_{2}
x
_{sp}
_{2}
x_{k}
_{1}
if the length of
P
is even.
Obviously, the length of
P
_{1}
is
p
+ 1, and thus
d_{G}
×
K_{r}
(
x_{i}
_{1}
,
x_{k}
_{1}
) ≤
p
+ 1 ≤
d_{G}
(
u_{i}, u_{k}
). If there were a (
x_{i}
_{1}
,
x_{k}
_{1}
)-path in
G
×
K_{r}
that is shorter than
p
+ 1 then it is easy to find a (
u_{i}, u_{k}
)-path in
G
that is also shorter than
p
+ 1 in contrast to
d_{G}
(
u_{i}, u_{k}
) =
p
+ 1. □
Theorem 3.2.
Let G be a connected graph with n
≥ 2
vertices and m edges. Then
Proof
. Set
V
(
G
) = {
u
_{1}
,
u
_{2}
, . . . ,
u_{n}
} and
V
(
K_{r}
) = {
v
_{1}
,
v
_{2}
, . . . ,
v_{r}
}. Let
x_{ij}
denote the vertex (
u_{i}, v_{j}
) of
G
×
K_{r}
. The degree of the vertex
x_{ij}
in
G
×
K_{r}
is
d_{G}
(
u_{i}
)
d_{Kr}
(
v_{j}
), that is
d_{G×Kr}
(
x_{ij}
) = (
r
− 1)
d_{G}
(
u_{i}
). By the definition of multiplicatively weighted Harary index
where
A
_{1}
to
A
_{3}
are the sums of the above terms, in order.
We shall calculate
A
_{1}
to
A
_{3}
of (1) separately.
(
A
_{1}
) First we compute
(
A
_{2}
) Next we compute
Let
E
_{1}
= {
uv
∈
E
(
G
) |
uv
is on a
C
_{3}
in
G
} and
E
_{2}
=
E
(
G
) −
E
_{1}
.
Now summing (3) over
j
= 0, 1, . . . ,
r
− 1, we get,
(
A
_{3}
) Next we compute
Using (1) and the sums
A
_{1}
,
A
_{2}
and
A
_{3}
in (2),(4) and (5), respectively, we have,
Using Theorem 3.2, we have the following corollaries.
Corollary 3.3.
Let G be a connected graph on n
≥ 2
vertices with m edges. If each edge of G is on a C
_{3}
,
then
For a triangle free graph
Corollary 3.4.
If G is a connected triangle free graph on n
≥ 2
vertices and m edges, then
By direct calculations we obtain expressions for the values of the Harary indices of
K_{n}
and
C_{n}
.
when
n
is even, and
otherwise. Similarly,
Using Corollaries 3.3 and 3.4, we obtain the multiplicatively weighted Harary indices of the graphs
K_{n}
×
K_{r}
and
C_{n}
×
K_{r}
.
Example 2.
(
i
)
(
ii
)
G
⊠
K_{r}
.
Theorem 4.1.
Let G be a connected graph with n vertices and m edges. Then
Proof
. Set
V
(
G
) = {
u
_{1}
,
u
_{2}
, . . . ,
u_{n}
} and
V
(
K_{r}
) = {
v
_{1}
,
v
_{2}
, . . . ,
v_{r}
}. Let
x_{ij}
denote the vertex (
u_{i}, v_{j}
) of
G
⊠
K_{r}
. The degree of the vertex
x_{ij}
in
G
⊠
K_{r}
is
d_{G}
(
u_{i}
) +
d_{Kr}
(
v_{j}
) +
d_{G}
(
u_{i}
)
d_{Kr}
(
v_{j}
), that is
d
_{G}
_{⊠}
_{Kr}
(
x_{ij}
) =
rd_{G}
(
u_{i}
) + (
r
− 1). One can see that for any pair of vertices
x_{ij}
,
x_{kp}
∈
V
(
G
⊠
K_{r}
),
d
_{G}
_{⊠}
_{Kr}
(
x_{ij}
,
x_{ip}
) = 1 and
d
_{G}
_{⊠}
_{Kr}
(
x_{ij}
,
x_{kp}
) =
d_{G}
(
u_{i}
,
u_{k}
).
where
A
_{1}
,
A
_{2}
and
A
_{3}
are the sums of the terms of the above expression, in order. We shall obtain
A
_{1}
to
A
_{3}
of (6), separately.
Using (7), (8) and (9) in (6), we have
Using Theorem 4.1, we obtain the following corollary.
Corollary 4.2.
As an application we present formula for multiplicatively weighted Harary index of closed fence graph,
C_{n}
⊠
K
_{2}
, see
Fig. 3
.
Closed fence graph
Example 3.
By Corolarry 4.2, we have
K. Pattabiraman received M.Sc. and Ph.D. from Annamalai University. Since 2006 he has been at Annamalai University. His research interests include Graph Theory and Mathematical Chemistry.
Department of Mathematics, Faculty of Engineering and Technology, Annamalai University Annamalainagar-608 002.
e-mail: pramank@gmail.com

1. Introduction

All the graphs considered in this paper are simple and connected. For vertices
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

2. Multiplicatively weighted Harary index ofG1+G2

In this section, we compute the Multiplicatively Weighted Harary Index of join of two graphs.
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

3. Multiplicatively weighted Harary index of tensor product of graphs

In this section, we compute the Multiplicatively weighted Harary index of
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

4. Multiplicatively weighted Harary index of strong product of graphs

In this section, we obtain the multiplicatively weighted Harary index of
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

BIO

Ashrafi A.R.
,
Doslic T.
,
Hamzeha A.
(2010)
The Zagreb coindices of graph operations
Discrete Appl. Math.
158
1571 -
1578
** DOI : 10.1016/j.dam.2010.05.017**

Alizadeh Y.
,
Iranmanesh A.
,
Doslic T.
(2013)
Additively weighted Harary index of some com-posite graphs
Discrete Math.
313
26 -
34
** DOI : 10.1016/j.disc.2012.09.011**

Ashrafi A.R.
,
Doslic T.
,
Hamzeha A.
(2011)
Extremal graphs with respect to the Zagreb coindices
MATCH Commun. Math.Comput. Chem.
65
85 -
92

Doslic T.
(2008)
Vertex-weighted Wiener polynomials for composite graphs
Ars Math. Contemp.
1
66 -
80

Dobrynin A.A.
,
Kochetova A.A.
(1994)
Degree distance of a graph: a degree analogue of the Wiener index
J. Chem. Inf. Comput. Sci.
34
1082 -
1086
** DOI : 10.1021/ci00021a008**

Devillers J.
,
Balaban A.T.
1999
Topological indices and related descriptors in QSAR and QSPR
Gordon and Breach
Amsterdam, The Netherlands

Das K.C.
,
Zhou B.
,
Trinajstic N.
(2009)
Bounds on Harary index
J. Math. Chem.
46
1369 -
1376
** DOI : 10.1007/s10910-009-9520-x**

Das K.C.
,
Xu K.
,
Cangul I.N.
,
Cevik A.S.
,
Graovac A.
(2013)
On the Harary index of graph operations
J. Inequal. Appl.
339 -
** DOI : 10.1186/1029-242X-2013-339**

Feng L.
,
Llic A.
(2010)
Zagreb, Harary and hyper-Wiener indices of graphs with a given matching number
Appl. Math. Lett.
23
943 -
948
** DOI : 10.1016/j.aml.2010.04.017**

Gutman I.
,
Das K.C.
(2004)
The first Zagerb index 30 years after
MATCH Commun. Math. Comput. Chem.
50
83 -
92

Gutman I.
,
Polansky O.E.
1986
Mathematical Concepts in Organic Chemistry
Springer-Verlag
Berlin

Gutman I.
(1994)
Selected properties of the Schultz molecular topogical index
J. Chem. Inf. Comput. Sci.
34
1087 -
1089
** DOI : 10.1021/ci00021a009**

Hoji M.
,
Luo Z.
,
Vumar E.
(2010)
Wiener and vertex PI indices of kronecker products of graphs
Discrete Appl. Math.
158
1848 -
1855
** DOI : 10.1016/j.dam.2010.06.009**

Hua H.
,
Zhang S.
(2012)
On the reciprocal degree distance of graphs
Discrete Appl. Math.
160
1152 -
1163
** DOI : 10.1016/j.dam.2011.11.032**

Hua H.
,
Zhang S.
Relations between Zagreb coindices and some distance-based topo-logical indices
MATCH Commun. Math.Comput. Chem.
in press

Ivanciuc O.
,
Balaban T.S.
(1993)
Reciprocal distance matrix, related local vertex invariants and topological indices
J. Math. Chem.
12
309 -
318
** DOI : 10.1007/BF01164642**

Khalifeh M.H.
,
Youseri-Azari H.
,
Ashrafi A.R.
(2008)
Vertex and edge PI indices of Cartesian product of graphs
Discrete Appl. Math.
156
1780 -
1789
** DOI : 10.1016/j.dam.2007.08.041**

Khalifeh M.H.
,
Yousefi-Azari H.
,
Ashrafi A. R.
(2009)
The first and second Zagreb indices of some graph operations
Discrete Appl. Math.
157
804 -
811
** DOI : 10.1016/j.dam.2008.06.015**

Lucic B.
,
Milicevic A.
,
Nikolic S.
,
Trinajstic N.
(2002)
Harary index-twelve years later
Croat. Chem. Acta
75
847 -
868

Plavsic D.
,
Nikolic S.
,
Trinajstic N.
,
Mihalic Z.
(1993)
On the Harary index for the charac-terization of chemical graphs
J. Math. Chem.
12
235 -
250
** DOI : 10.1007/BF01164638**

Pattabiraman K.
,
Paulraja P.
(2012)
On some topological indices of the tensor product of graphs
Discrete Appl. Math.
160
267 -
279
** DOI : 10.1016/j.dam.2011.10.020**

Pattabiraman K.
,
Paulraja P.
(2012)
Wiener and vertex PI indices of the strong product of graphs
Discuss. Math. Graph Thoery
32
749 -
769
** DOI : 10.7151/dmgt.1647**

Pattabiraman K.
,
Paulraja P.
(2011)
Wiener index of the tensor product of a path and a cycle
Discuss. Math. Graph Thoery
31
737 -
751
** DOI : 10.7151/dmgt.1576**

Pattabiraman K.
,
Vijaragavan M.
(2013)
Reciprocal degree distance of some graph operations
Trans. Combin.
2
13 -
24

Pattabiraman K.
,
Vijaragavan M.
Reciprocal degree distance of product graphs
Dis-crete Appl. Mathematics.

Su G.
,
Gutman I.
,
Xiong L.
,
Xu L.
Reciprocal product degree distance of graphs, Manuscript

Wang H.
,
Kang L.
(2013)
More on the Harary index of cacti
J. Appl. Math. Comput.
43
369 -
386
** DOI : 10.1007/s12190-013-0668-y**

Xu K.
,
Das K.C.
(2011)
On Harary index of graphs
Dis. Appl. Math.
159
1631 -
1640
** DOI : 10.1016/j.dam.2011.06.003**

Xu K.
,
Das K.C.
,
Hua H.
,
Diudea M.V.
(2013)
Maximal Harary index of unicyclic graphs with given matching number
Stud. Univ. Babes-Bolyai Chem.
58
71 -
86

Xu K.
,
Wang J.
,
Liu H.
The Harary index of ordinary and generalized quasi-tree graphs
J. Appl. Math. Comput.
** DOI : 10.1007/s12190-013-0727-4**

Yousefi-Azari H.
,
Khalifeh M.H.
,
Ashrafi A.R.
(2011)
Calculating the edge Wiener and edge Szeged indices of graphs
J. Comput. Appl. Math.
235
4866 -
4870
** DOI : 10.1016/j.cam.2011.02.019**

Zhou B.
,
Du Z.
,
Trinajstic N.
(2008)
Harary index of landscape graphs
Int. J. Chem. Model.
1
35 -
44

Zhou B.
,
Cai X.
,
Trinajstic N.
(2008)
On the Harary index
J. Math. Chem.
44
611 -
618
** DOI : 10.1007/s10910-007-9339-2**

Citing 'MULTIPLICATIVELY WEIGHTED HARARY INDICES OF GRAPH OPERATIONS
'

@article{ E1MCA9_2015_v33n1_2_89}
,title={MULTIPLICATIVELY WEIGHTED HARARY INDICES OF GRAPH OPERATIONS}
,volume={1_2}
, url={http://dx.doi.org/10.14317/jami.2015.089}, DOI={10.14317/jami.2015.089}
, number= {1_2}
, journal={Journal of Applied Mathematics & Informatics}
, publisher={Korean Society of Computational and Applied Mathematics}
, author={K. PATTABIRAMAN}
, year={2015}
, month={Jan}