Chemistry Reference
In-Depth Information
We now recall some algebraic definitions used here. Suppose
G
is a simple graph
and
{
u,v
} ⊆
V(G). A
path
connecting u and v in G is a sequence:
u=u
0
,e
1
,u
1
,e
2
,
...
,e
n
,u
n
= v
(6.2)
of distinct vertices u
1
,
...
,u
n
and distinct edges e
1
,
...
,e
n
such that e
i
is an edge
with end vertices u
i
−
1
and u
i
. The
distance
d(u, v) is define to be the length of a
minimal path connecting u and v. The half-summation of all distances between pairs
of vertices in
G
is called the
Wiener index
of
G
which is denoted by
W(G)
. The Wiener
index has been the first distance-based graph invariant and it was introduced by an
the American chemist Harold Wiener (
1947
). Suppose
e
uv
individuates an edge
in
G
. Define quantities m
u
(e) and m
v
(e) as follows: m
u
(e) is defined as the number of
edges lying closer to the vertex u than the vertex v, and m
v
(e) is defined analogously.
The edges equidistant from both ends of the edge uv are not counted. In a similar
way, we define n
u
(e) to be the number of vertices lying closer to the vertex u than v.
The
PI index
(Khadikar et al.
2001
) of G is defined as
=
e=uv
[m
u
(e)
PI(G)
=
+
m
v
(e)]
(6.3)
For acyclic molecular graphs
G
, Wiener discovered a remarkably simple algorithm
for computing
W(G)
. To explain his method, we assume that
e
ij
is an edge of
G
,
N(i)
is the number of vertices of
G
lying closer to
i
than to
j
and
N(j)
is defined
analogously. Thus,
=
N
(
i
)
=|{
u
∈
V
(
G
)
|
d
(
u
,
i
)
<d
(
u
,
j
)
}|
and
N
(
j
)
= |{
u
∈
V
(
G
)
|
d
(
u
,
j
)
<d
(
u
,
i
)
}|
(6.4)
Then the
Szeged index
of
G
is defined as the half-summation of all products
N(i)N(j)
over all graph edges
e
ij
. This generalization was conceived by Ivan Gutman (
1994
)
at the Attila Jozsef University in Szeged, and so it was called the Szeged index. It is
useful to mention here that Gutman in his 1994 paper proposed the existence of the
cyclic index and abbreviated it by W*. In that paper he has not given any name to
this index. Khadikar et al. (
1995
) used the name “Szeged index” and abbreviated as
Sz. According to a long-known result in the theory of graph distances, if
G
is a tree
then
Sz(G)
=
W(G)
, reproducing Wiener's original method.
Klavžar et al.
=
(
1996
) proved that for every connected graph
G
we have
≤
W(G)
Sz(G)
. So it is natural to ask about equality of these graph invariants. To
find a characterization of graphs satisfy the equality, we need some notation. A max-
imal 2-connected subgraph of a connected graph G is called a
block
of G. The block
graphs are those in which every block is a clique. Dobrynin and Gutman (
1995
) inves-
tigated the structure of a connected graph G featuring the property that
Sz(G)
=
W(G)
.
They proved that
Sz(G)
W(G) if and only if G is a block graph
(Dobrynin et al.
1995
). A new proof for this result is recently published (Khodashenas et al.
2011
).
The Wiener, PI and Szeged indices are all distance based invariants of a graph.
There are some other graph invariants based on degree sequence of the molecular
=
