The Graovac-Pisanski index of connected bipartite graphs with applications to hydrocarbon molecules

1. Introduction

In[1] we are able to discover the next definition: “The molecular descriptor is the ultimate results of a logic and mathematical process which transforms chemical info encoded inside a symbolic illustration of a molecule right into a helpful quantity or the results of some standardized experiment.”

For the reason that seminal analysis by Wiener from 1947[2] many molecular descriptors, i.e., graph invariants, had been launched. Completely different variations of the Wiener index have been identified since then, certainly one of them being the Graovac-Pisanski index,[Three] additionally referred to as the modified Wiener index. The benefit of this index compared to different distance-based indices is within the encountering of the symmetries of a graph, because the symmetries of a molecule have an affect on its properties.[four]

On one aspect, the mathematical properties of the Graovac-Pisanski index had been investigated. For instance, the index was intensely studied for nanostructures,[5–10] some basic outcomes on the Graovac-Pisanski index had been obtained,[11,12] the closed formulae for carbon nanotubes had been calculated,[13,14] extremal timber had been thought of,[15] and the symmetries of molecules had been studied.[16,17] On the opposite aspect, the chemical usefulness of the Graovac-Pisanski index was proven in,[18] the place the reference to the topological effectivity was thought of and later in,[19] the place the correlation with the melting factors of some households of hydrocarbon molecules was established. This was carried out with using the QSPR evaluation and for all of the thought of molecular graphs from[19] the Graovac-Pisanski index is an integer quantity. Naturally, the query whether or not the Graovac-Pisanski index is an integer quantity for all linked graphs arises by this commentary.

We proceed as follows. Within the subsequent part, some fundamental notation is launched and necessary definitions are included. In Part Three, we show that the Graovac-Pisanski index of any linked bipartite graph is an integer quantity. Furthermore, we present that the identical conclusion holds additionally for any linked graph with a good variety of vertices. Specifically, which means for numerous molecular graphs the Graovac-Pisanski index is an integer, what’s defined in Part four. In the identical part, the closed components for the Graovac-Pisanski index of an infinite household of nanotubical fullerenes is deduced. Lastly, in Part 5 we use a pc programme to acquire the variety of linked graphs on at most 9 vertices for which the Graovac-Pisanski index just isn’t an integer. An infinite household of graphs with a non-integer Graovac-Pisanski index can be included.

2. Preliminaries

All of the graphs thought of on this paper are easy, finite and linked. The distance

dG(u,v)

between vertices u and v of a graph G is the size of a shortest path between vertices u and v in G. A bipartite graph is a graph whose vertices will be divided into two disjoint units U and V such that each edge connects a vertex in U to 1 in V. Vertex subsets U and V might be referred to as the bipartite units of the graph.

The Wiener index of a linked graph G is outlined as follows:

W(G)=V(G)dG(u,v).

Additionally, for any

SV(G)

we outline

WG(S)=SdG(u,v).

An isomorphism of graphs G and H is a bijection

f:V(G)V(H),

such that for any two vertices u and v from G it holds that u and v are adjoining in G if and provided that f(u) and f(v) are adjoining in H. If

f:V(G)V(G)

is an isomorphism then the perform f is named an automorphism of the graph G. It’s straightforward to verify that the composition of two automorphisms is one other automorphism. Furthermore, the set of all automorphisms of a given graph G, underneath the composition operation, types the automorphism group of G, denoted by

Aut(G).

Let G be a linked graph. The Graovac-Pisanski index of G is outlined as

GP(G)=|V(G)|2|Aut(G)|uV(G)αAut(G)dG(u,α(u)).

Allow us to point out, that for the Graovac-Pisanski index, also called the modified Wiener index, the notation

Ŵ(G)

is used, however to clear the confusion within the space of variations of the Wiener indices, we use the title Graovac-Pisanski index, as urged in[12] and denote it with the

GP(G).

Lastly, we embrace some fundamental definitions from group principle. If G is a bunch and X is a set, then a group motion

ϕ

of G on X is a perform

ϕ:G×XX

that satisfies the next:

ϕ(e,x)=x

for any

xX

(right here, e is the impartial aspect of G) and

ϕ(gh,x)=ϕ(g,ϕ(h,x))

for all

g,hG

and

xX.

The orbit of a component x in X is the set of parts in X to which x will be moved by the weather of G, i.e., the set

 gG.

If G is a graph and

Aut(G)

the automorphism group, then

ϕ:Aut(G)×V(G)V(G),

outlined by

ϕ(α,u)=α(u)

for any

αAut(G),uV(G),

is named the pure motion of the group

Aut(G)

on V(G).

It was proven by Graovac and Pisanski[Three] that if

V1,,Vt

are the orbits underneath the pure motion of the group

Aut(G)

on V(G), then (1)

GP(G)=|V(G)|i=1t1|Vi|WG(Vi).

(1)

Three. Essential outcomes

On this part we show the primary results of the paper, i.e., the Graovac-Pisanski index of any linked bipartite graph is all the time an integer quantity.

First, we’ll rewrite the Graovac-Pisanski index in one other type. For this goal, we want some extra definitions. Let G be a graph and let

uV(G).

The distance of u in G,

wG(u),

is the sum of distances from u to all the opposite vertices of G. That’s,

wG(u)=vV(G)dG(u,v).

Furthermore, if

SV(G)

and

uV(G),

then

wS(u)=vSdG(u,v).

Utilizing the space, one can rewrite the Wiener index for

SV(G)

as follows (2)

WG(S)=12uSwS(u).

(2)

Proposition Three.1.

Let G be a linked graph and let

v1,,vt

be the representatives of orbits

V1,,Vt

underneath the pure motion of the group

Aut(G)

on V(G). Then

(Three)

GP(G)=|V(G)|i=1t12wVi(vi).

(Three) Proof

If two vertices u, v are in the identical orbit Vi,

i1,,t,

then it clearly holds

wVi(u)=wVi(v).

Since all of the vertices in the identical orbit have the exact same sum of distances, inserting (2) into (1) we get

GP(G)=|V(G)|i=1t|Vi|·wVi(vi)2|Vi|=|V(G)|i=1t12wVi(vi)

and the required end result follows. □

By (Three) we get the next observations.

Corollary Three.2.

If G is a linked graph with a good variety of vertices, then

GP(G)

is an integer quantity.

Corollary Three.Three.

The Graovac-Pisanski index of any linked graph is both an integer or half of an integer quantity.

Nevertheless, if G is bipartite, we are able to say extra. The next result’s the primary results of this paper.

Theorem Three.four.

If G is a linked bipartite graph, then

GP(G)

is an integer quantity.

Proof.

Let G be a bipartite graph and let U, V be the bipartition of V(G). That’s, no edge connects two vertices of U and no edge connects two vertices of V. We contemplate two instances:

  1. There’s

    ψAut(G)

    such that

    ψ(u)=v

    for some

    uU

    and

    vV.

On this case, we’ll present that ψ reverses the bipartite units, i.e.

ψ(x)V

for any

xU

and

ψ(y)U

for any

yV.

To show this, suppose that

xU

however

ψ(x)

additionally belongs to U. Since

u,xU,

the space

dG(u,x)

is a good quantity. Subsequently, since ψ is an automorphism,

dG(ψ(u),ψ(x))=dG(u,x)

should be even, too. Since

ψ(u)=v,

we receive that

dG(v,ψ(x))

is even. However

ψ(x)U

and

vV

and due to this fact, this can be a contradiction. In an analogous means one can present

ψ(y)U

for any

yV.

We have now proved that ψ reverses the bipartite units. Furthermore, the restriction of ψ on U,

ψ|U,

is a bijection from U to V. Consequently,

|U|=|V|

and

|V(G)|

is even. By Corollary Three.2, the Graovac-Pisanski index of G is an integer quantity.

ii. There is no such thing as a automorphism that reverses the bipartite units.

On this case, if u and v are two vertices from the identical orbit, these two vertices are additionally in the identical bipartite set. Subsequently, the space between them should be even. Consequently, if

v1,,vt

are the representatives of orbits

V1,,Vt

underneath the pure motion of the group

Aut(G)

on V(G), all of the distances

wVi(vi)

are even in (Three), and so the Graovac-Pisanski index is once more an integer quantity.

For the reason that Graovac-Pisanski index is an integer quantity in each instances, the proof is full. □

four. Functions to molecular graphs

On this part we apply our predominant outcomes to some well-known molecular graphs.

four.1. Paraffins, benzenoid hydrocarbons, phenylenes and carbon nanotubes

Paraffins (alkanes) are mathematically modeled by chemical timber, i.e., timber during which each vertex has diploma at most 4.

Let

H

be the hexagonal (graphite) lattice and let Z be a cricuit on it. Then a benzenoid system is induced by the vertices and edges of

H,

mendacity on Z and in its inside. In chemistry a benzenoid system is a mathematical mannequin for a benzenoid hydrocarbon. Let G be a benzenoid system. A vertex shared by three hexagons of G is named an inside vertex of G. A benzenoid system is alleged to be catacondensed if it doesn’t possess inside vertices. In any other case it’s referred to as pericondensed. Two distinct hexagons with a typical edge are referred to as adjoining. Let G be a catacondensed benzenoid system. If we add squares between all pairs of adjoining hexagons of G, the obtained graph

G

is named a phenylene, see Determine 1.

Determine 1. A benzenoid system G and corresponding phenylene

G.

Subsequent we formally outline open-ended carbon nanotubes, additionally referred to as tubulenes. Select any lattice level within the hexagonal lattice because the origin O. Let

a1

and

a2

be the 2 fundamental lattice vectors. Select a vector

OA=na1+ma2

such that n and m are two integers and

|n|+|m|>1,nm1.

Draw two straight traces L1 and L2 passing by O and A perpendicular to

OA,

respectively. By rolling up the hexagonal strip between L1 and L2 and gluing L1 and L2 such that A and O superimpose, we are able to receive a hexagonal tessellation

HT

of the cylinder. L1 and L2 point out the path of the axis of the cylinder. Utilizing the terminology of graph principle, a tubulene G is outlined to be the finite graph induced by all of the hexagons of

HT

that lie between c1 and c2, the place c1 and c2 are two vertex-disjoint cycles of

HT

encircling the axis of the cylinder.

For any tubulene G, if its chiral vector is

na1+ma2,

G might be referred to as an (n, m)-type tubulene, see Determine 2[13. If G is a (n, m)-type tubulene the place n = zero or m = zero, we name it a zig-zag tubulene.

Determine 2. A (6, zero)-type tubulene (zig-zag tubulene).

Proposition four.1.

Let G be a paraffin, a benzenoid system, a phenylene or a tubulene. The Graovac-Pisanski index of G is an integer quantity.

Proof.

Clearly each paraffin is a bipartite graph and the identical holds for benzenoid programs and phenylenes. It was proven in[20] that tubulenes are bipartite graphs as nicely. Subsequently, by Theorem Three.four the Graovac-Pisanski index of G is an integer quantity. □

four.2. Fullerenes

A fullerene G is a Three-connected Three-regular aircraft graph such that each face is bounded by both a pentagon or a hexagon, see Determine Three (clearly, fullerenes usually are not bipartite graphs). By Euler’s components, it follows that the variety of pentagonal faces of a fullerene is precisely 12. For extra info on fullerenes see.[21]

The next end result concerning the Graovac-Pisanski index of fullerenes can now be said.

Proposition four.2.

Let G be a fullerene. The Graovac-Pisanski index of G is an integer quantity.

Proof.

Since all vertices in a fullerene have odd levels, the graph should have even variety of vertices. (It’s well-known that a fullerene with n vertices exists for any even

n24

and for n = 20, for the small print see Theorem 2.2 in.[21]) Therefore, by Corollary Three.2 it follows that the Graovac-Pisanski index of G is an integer quantity.□

To conclude the part, we compute the Graovac-Pisanski index of an infinite household of nanotubical fullerenes denoted by Fn,

n1.

Specifically, Fn is obtained by the (6, zero)-type tubulene with n layers of hexagons (zig-zag tubulene such that each layer comprises 6 hexagons), closed with two caps proven in Determine four.22

We’ll use Proposition Three.1 to calculate the Graovac-Pisanski index of Fn. The orbits and corresponding representatives within the cap A are denoted by Vi and vi,

i1,,6.

The orbits and corresponding representatives of the cap B are denoted by Ui and ui,

i1,,eight.

First, we compute the distances of vertices vi,

i1,,6,

within the corresponding orbits:

wV1(v1)=2+four+6=12,

wV2(v2)=2+four+5=11,

wVThree(vThree)=6,

wVfour(vfour)=5,

wV5(v5)=Three,

wV6(v6)=1+2+Three=6.

The sum of all these distances is 43.

Furthermore, we calculate the distances of vertices ui,

i1,,eight,

within the corresponding orbits:

wU1(u1)=2+four+6=12,

wU2(u2)=2+four+6=12,

wUThree(uThree)=6,

wUfour(ufour)=6,

wU5(u5)=four,

wU6(u6)=1+four+5=10,

wU7(u7)=2+2+Three=7,

wUeight(ueight)=1.

The sum of all these distances is 58. The orbits and the distances of the layers within the tubical half are analogous to the orbits Ui and distances

wUi(ui),i1,2,Three,four.

Clearly, it holds

|V(Fn)|=12(n+1)+6+12=12n+30.

Subsequently, by Proposition Three.1 we conclude

GP(Fn)=12n+302(43+58+36(n1))=216n2+930n+975.

We observe that the Graovac-Pisanski index of fullerene Fn is an integer quantity for any

n1.

Additionally, the Graovac-Pisanski index of two different households of nanotubical fullerenes was computed in[18] and the result’s once more an integer quantity, what coincides with Proposition four.2.

5. Graphs for which the Graovac-Pisanski index just isn’t an integer

By Theorem Three.four, Corollary Three.2, and Proposition four.2, many chemical graphs have integer Graovac-Pisanski index (for instance the fullerene graphs, timber, hexagonal buildings, and so on.). In fact, there are additionally linked graphs whose Graovac-Pisanski index just isn’t an integer. The smallest such graph comprises 5 vertices.

In Desk 1 we current the variety of linked graphs on n vertices,

nThree,5,7,9,

whose Graovac-Pisanski index just isn’t an integer quantity. The outcomes had been obtained by utilizing a pc programme.

Desk 1. Variety of linked graphs on Three, 5, 7, and 9 vertices, divided in these with an integer and people with a non-integer Graovac-Pisanski index.

In Determine 5 we are able to see all of the linked graphs on 5 vertices whose Graovac-Pisanski index just isn’t an integer quantity.

Determine 5. All linked graphs on 5 vertices for which the Graovac-Pisanski index just isn’t an integer.

The next theorem presents an infinite class of unicyclic graphs for which the Graovac-Pisanski index just isn’t an integer quantity.

Theorem 5.1.

Let G be a graph consisting of a cycle of wierd size, the place

Three or 5(mod eight)

, to which we connect a path of even size t, the place t is a constructive integer. Then G has

+t

vertices and

GP(G)

just isn’t an integer quantity.

Proof.

In G there are

12

orbits with two vertices and t + 1 orbits with one vertex. Let z be the vertex of diploma Three in G. Then the orbits with two vertices comprise pairs of vertices on the identical distance from z. Therefore, the distances between the pairs of vertices from the identical orbit are

1,2,,12

and

GP(G)=|V(G)|·12·(1+2++12)=|V(G)|·12·((+1)/22).

It’s straightforward to watch that the quantity

|V(G)|=+t

is odd and consequently, the Graovac-Pisanski index just isn’t an integer if and provided that the quantity representing the binomial coefficient,

12+1212,

is odd. □

An instance of a graph satisfying assumptions of Theorem 5.1 is introduced because the final graph in Determine 5.

Lastly, we additionally comment that if G is a twin of a fullerene, then

GP(G)

will be an integer quantity or not an integer quantity, what is clear from the ends in.[18]

Supply

Leave a Comment