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

Abstract

The Graovac-Pisanski index, also called the modified Wiener index, was introduced in 1991 and represents an extension of the original Wiener index, because it considers beside the distances in a graph also its symmetries. Similarly as Wiener in 1947 showed the correlation of the Wiener indices of the alkane series with the boiling points, in 2018 the connection between the Graovac-Pisanski index and the melting points of some hydrocarbon molecules was established. In this paper, we prove that the Graovac-Pisanski index of any connected bipartite graph as well as of any connected graph on an even number of vertices is an integer number. These results are applied to some important families of hydrocarbon molecules. By using a computer programme, the graphs with a non-integer Graovac-Pisanski index on at most nine vertices are counted. Finally, an infinite class of unicyclic graphs with a non-integer Graovac-Pisanski index is described.

Keywords:

• Modified Wiener index
• Graovac-Pisanski index
• graph distance
• automorphism group
• hydrocarbons
• carbon nanostructures

AMS Subject Classification:

• 05C92
• 05C09
• 92E10
• 05C12

1. Introduction

In^[1] we can find the following definition: “The molecular descriptor is the final result of a logic and mathematical procedure which transforms chemical information encoded within a symbolic representation of a molecule into a useful number or the result of some standardized experiment.”

Since the seminal research by Wiener from 1947^[2] many molecular descriptors, i.e., graph invariants, were introduced. Different variations of the Wiener index have been known since then, one of them being the Graovac-Pisanski index,^[3] also called the modified Wiener index. The advantage of this index in comparison to other distance-based indices is in the encountering of the symmetries of a graph, since the symmetries of a molecule have an influence on its properties.^[4]

On one side, the mathematical properties of the Graovac-Pisanski index were investigated. For example, the index was intensely studied for nanostructures,^[5–10] some general results on the Graovac-Pisanski index were obtained,^[11,12] the closed formulae for carbon nanotubes were calculated,^[13,14] extremal trees were considered,^[15] and the symmetries of molecules were studied.^[16,17] On the other side, the chemical usefulness of the Graovac-Pisanski index was shown in,^[18] where the connection with the topological efficiency was considered and later in,^[19] where the correlation with the melting points of some families of hydrocarbon molecules was established. This was done with the use of the QSPR analysis and for all the considered molecular graphs from^[19] the Graovac-Pisanski index is an integer number. Naturally, the question whether the Graovac-Pisanski index is an integer number for all connected graphs arises by this observation.

We proceed as follows. In the next section, some basic notation is introduced and important definitions are included. In Section 3, we prove that the Graovac-Pisanski index of any connected bipartite graph is an integer number. Moreover, we show that the same conclusion holds also for any connected graph with an even number of vertices. In particular, this means that for various molecular graphs the Graovac-Pisanski index is an integer, what is explained in Section 4. In the same section, the closed formula for the Graovac-Pisanski index of an infinite family of nanotubical fullerenes is deduced. Finally, in Section 5 we use a computer programme to obtain the number of connected graphs on at most nine vertices for which the Graovac-Pisanski index is not an integer. An infinite family of graphs with a non-integer Graovac-Pisanski index is also included.

2. Preliminaries

All the graphs considered in this paper are simple, finite and connected. The distance $d_G(u,v)$ between vertices u and v of a graph G is the length of a shortest path between vertices u and v in G. A bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V. Vertex subsets U and V will be called the bipartite sets of the graph.

The Wiener index of a connected graph G is defined as follows: $$W(G)=\sum _{\{u,v\}\subseteq V(G)}{d}_G(u,v).$$

Also, for any $S\subseteq V(G)$ we define $$W_G(S)=\sum _{\{u,v\}\subseteq S}{d}_G(u,v).$$

An isomorphism of graphs G and H is a bijection $f:V(G)\to V(H),$ such that for any two vertices u and v from G it holds that u and v are adjacent in G if and only if f(u) and f(v) are adjacent in H. If $f:V(G)\to V(G)$ is an isomorphism then the function f is called an automorphism of the graph G. It is easy to check that the composition of two automorphisms is another automorphism. Moreover, the set of all automorphisms of a given graph G, under the composition operation, forms the automorphism group of G, denoted by $\text{Aut}(G).$

Let G be a connected graph. The Graovac-Pisanski index of G is defined as $$\text{GP}(G)=\frac{|V(G)|}{2|\text{Aut}(G)|}\sum _{u\in V(G)}\sum _{\alpha \in \text{Aut}(G)}{d}_G(u,\alpha (u)).$$

Let us mention, that for the Graovac-Pisanski index, also known as the modified Wiener index, the notation $\widehat{W}(G)$ is used, but to clear the confusion in the area of variations of the Wiener indices, we use the name Graovac-Pisanski index, as suggested in^[12] and denote it with the $\text{GP}(G).$

Finally, we include some basic definitions from group theory. If G is a group and X is a set, then a group action $\varphi$ of G on X is a function $\varphi :G\times X\to X$ that satisfies the following: $\varphi (e,x)=x$ for any $x\in X$ (here, e is the neutral element of G) and $\varphi (gh,x)=\varphi (g,\varphi (h,x))$ for all $g,h\in G$ and $x\in X.$ The orbit of an element x in X is the set of elements in X to which x can be moved by the elements of G, i.e., the set $\{\varphi (g,x) | g\in G\}.$ If G is a graph and $\text{Aut}(G)$ the automorphism group, then $\varphi :\text{Aut}(G)\times V(G)\to V(G),$ defined by $\varphi (\alpha ,u)=\alpha (u)$ for any $\alpha \in \text{Aut}(G),u\in V(G),$ is called the natural action of the group $\text{Aut}(G)$ on V(G).

It was shown by Graovac and Pisanski^[3] that if $V_1,\dots ,V_t$ are the orbits under the natural action of the group $\text{Aut}(G)$ on V(G), then (1) $$\text{GP}(G)=|V(G)|\sum _{i=1}^t\frac{1}{\left|V_i\right|}{W}_G(V_i).$$(1)

3. Main results

In this section we prove the main result of the paper, i.e., the Graovac-Pisanski index of any connected bipartite graph is always an integer number.

First, we will rewrite the Graovac-Pisanski index in another form. For this purpose, we need some additional definitions. Let G be a graph and let $u\in V(G).$ The distance of u in G, $w_G(u),$ is the sum of distances from u to all the other vertices of G. That is, $w_G(u)=\sum _{v\in V(G)}{d}_G(u,v).$ Moreover, if $S\subseteq V(G)$ and $u\in V(G),$ then $w_S(u)=\sum _{v\in S}{d}_G(u,v).$ Using the distance, one can rewrite the Wiener index for $S\subseteq V(G)$ as follows (2) $$W_G(S)=\frac{1}{2}\sum _{u\in S}{w}_S(u).$$(2)

Proposition 3.1.

Let G be a connected graph and let $v_1,\dots ,v_t$ be the representatives of orbits $V_1,\dots ,V_t$ under the natural action of the group $\text{Aut}(G)$ on V(G). Then

(3) $$\text{GP}\left(G\right)=\left|V\right(G\left)\right|\sum _{i=1}^t\frac{1}{2}{w}_{V_i}\left(v_i\right).$$(3)

Proof

If two vertices u, v are in the same orbit V_i, $i\in \{1,\dots ,t\},$ then it obviously holds $w_{V_i}(u)=w_{V_i}(v).$ Since all the vertices in the same orbit have the very same sum of distances, inserting (2) into (1) we get $$\text{GP}(G)=|V(G)|\sum _{i=1}^t\frac{\left|V_i\right|·w_{V_i}(v_i)}{2\left|V_i\right|}=|V(G)|\sum _{i=1}^t\frac{1}{2}{w}_{V_i}(v_i)$$ and the required result follows. □

By (3) we get the following observations.

Corollary 3.2.

If G is a connected graph with an even number of vertices, then $\text{GP}(G)$ is an integer number.

Corollary 3.3.

The Graovac-Pisanski index of any connected graph is either an integer or half of an integer number.

However, if G is bipartite, we can say more. The following result is the main result of this paper.

Theorem 3.4.

If G is a connected bipartite graph, then $\text{GP}(G)$ is an integer number.

Proof.

Let G be a bipartite graph and let U, V be the bipartition of V(G). That is, no edge connects two vertices of U and no edge connects two vertices of V. We consider two cases:

1. There is $\psi \in \text{Aut}(G)$ such that $\psi (u)=v$ for some $u\in U$ and $v\in V.$

In this case, we will show that ψ reverses the bipartite sets, i.e. $\psi (x)\in V$ for any $x\in U$ and $\psi (y)\in U$ for any $y\in V.$ To prove this, suppose that $x\in U$ but $\psi (x)$ also belongs to U. Since $u,x\in U,$ the distance $d_G(u,x)$ is an even number. Therefore, since ψ is an automorphism, $d_G(\psi (u),\psi (x))=d_G(u,x)$ must be even, too. Since $\psi (u)=v,$ we obtain that $d_G(v,\psi (x))$ is even. But $\psi (x)\in U$ and $v\in V$ and therefore, this is a contradiction. In a similar way one can show $\psi (y)\in U$ for any $y\in V.$ We have proved that ψ reverses the bipartite sets. Moreover, the restriction of ψ on U, $\psi {|}_U,$ is a bijection from U to V. Consequently, $\left|U\right|=\left|V\right|$ and $|V(G)|$ is even. By Corollary 3.2, the Graovac-Pisanski index of G is an integer number.

ii. There is no automorphism that reverses the bipartite sets.

In this case, if u and v are two vertices from the same orbit, these two vertices are also in the same bipartite set. Therefore, the distance between them must be even. Consequently, if $v_1,\dots ,v_t$ are the representatives of orbits $V_1,\dots ,V_t$ under the natural action of the group $\text{Aut}(G)$ on V(G), all the distances $w_{V_i}(v_i)$ are even in (3), and so the Graovac-Pisanski index is again an integer number.

Since the Graovac-Pisanski index is an integer number in both cases, the proof is complete. □

4. Applications to molecular graphs

In this section we apply our main results to some well-known molecular graphs.

4.1. Paraffins, benzenoid hydrocarbons, phenylenes and carbon nanotubes

Paraffins (alkanes) are mathematically modeled by chemical trees, i.e., trees in which every vertex has degree at most four.

Let $\mathcal{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 $\mathcal{H},$ lying on Z and in its interior. In chemistry a benzenoid system is a mathematical model for a benzenoid hydrocarbon. Let G be a benzenoid system. A vertex shared by three hexagons of G is called an internal vertex of G. A benzenoid system is said to be catacondensed if it does not possess internal vertices. Otherwise it is called pericondensed. Two distinct hexagons with a common edge are called adjacent. Let G be a catacondensed benzenoid system. If we add squares between all pairs of adjacent hexagons of G, the obtained graph $G\prime$ is called a phenylene, see Figure 1.

Figure 1. A benzenoid system G and corresponding phenylene $G\prime .$

Next we formally define open-ended carbon nanotubes, also called tubulenes. Choose any lattice point in the hexagonal lattice as the origin O. Let $\overrightarrow{a_1}$ and $\overrightarrow{a_2}$ be the two basic lattice vectors. Choose a vector $\overrightarrow{OA}=n\overrightarrow{a_1}+m\overrightarrow{a_2}$ such that n and m are two integers and $\left|n\right|+\left|m\right|>1,nm\ne -1.$ Draw two straight lines L₁ and L₂ passing through O and A perpendicular to $OA,$ respectively. By rolling up the hexagonal strip between L₁ and L₂ and gluing L₁ and L₂ such that A and O superimpose, we can obtain a hexagonal tessellation $\mathcal{H}\mathcal{T}$ of the cylinder. L₁ and L₂ indicate the direction of the axis of the cylinder. Using the terminology of graph theory, a tubulene G is defined to be the finite graph induced by all the hexagons of $\mathcal{H}\mathcal{T}$ that lie between c₁ and c₂, where c₁ and c₂ are two vertex-disjoint cycles of $\mathcal{H}\mathcal{T}$ encircling the axis of the cylinder.

For any tubulene G, if its chiral vector is $n\overrightarrow{a_1}+m\overrightarrow{a_2},$ G will be called an (n, m)-type tubulene, see Figure 2^[13. If G is a (n, m)-type tubulene where n = 0 or m = 0, we call it a zig-zag tubulene.

Figure 2. A (6, 0)-type tubulene (zig-zag tubulene).

Proposition 4.1.

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

Proof.

Obviously every paraffin is a bipartite graph and the same holds for benzenoid systems and phenylenes. It was shown in^[20] that tubulenes are bipartite graphs as well. Therefore, by Theorem 3.4 the Graovac-Pisanski index of G is an integer number. □

4.2. Fullerenes

A fullerene G is a 3-connected 3-regular plane graph such that every face is bounded by either a pentagon or a hexagon, see Figure 3 (obviously, fullerenes are not bipartite graphs). By Euler’s formula, it follows that the number of pentagonal faces of a fullerene is exactly 12. For more information on fullerenes see.^[21]

Figure 3. A fullerene G.

The following result about the Graovac-Pisanski index of fullerenes can now be stated.

Proposition 4.2.

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

Proof.

Since all vertices in a fullerene have odd degrees, the graph must have even number of vertices. (It is well known that a fullerene with n vertices exists for any even $n\ge 24$ and for n = 20, for the details see Theorem 2.2 in.^[21]) Hence, by Corollary 3.2 it follows that the Graovac-Pisanski index of G is an integer number.□

To conclude the section, we compute the Graovac-Pisanski index of an infinite family of nanotubical fullerenes denoted by F_n, $n\ge 1.$ In particular, F_n is obtained by the (6, 0)-type tubulene with n layers of hexagons (zig-zag tubulene such that every layer contains 6 hexagons), closed with two caps shown in Figure 4.²²

Figure 4. Caps A and B for the fullerene F_n.

We will use Proposition 3.1 to calculate the Graovac-Pisanski index of F_n. The orbits and corresponding representatives in the cap A are denoted by V_i and v_i, $i\in \{1,\dots ,6\}.$ The orbits and corresponding representatives of the cap B are denoted by U_i and u_i, $i\in \{1,\dots ,8\}.$

First, we compute the distances of vertices v_i, $i\in \{1,\dots ,6\},$ in the corresponding orbits: $w_{V_1}(v_1)=2+4+6=12,$ $w_{V_2}(v_2)=2+4+5=11,$ $w_{V_3}(v_3)=6,$ $w_{V_4}(v_4)=5,$ $w_{V_5}(v_5)=3,$ $w_{V_6}(v_6)=1+2+3=6.$ The sum of all these distances is 43.

Moreover, we calculate the distances of vertices u_i, $i\in \{1,\dots ,8\},$ in the corresponding orbits: $w_{U_1}(u_1)=2+4+6=12,$ $w_{U_2}(u_2)=2+4+6=12,$ $w_{U_3}(u_3)=6,$ $w_{U_4}(u_4)=6,$ $w_{U_5}(u_5)=4,$ $w_{U_6}(u_6)=1+4+5=10,$ $w_{U_7}(u_7)=2+2+3=7,$ $w_{U_8}(u_8)=1.$ The sum of all these distances is 58. The orbits and the distances of the layers in the tubical part are analogous to the orbits U_i and distances $w_{U_i}(u_i),i\in \{1,2,3,4\}.$

Obviously, it holds $|V(F_n)|=12(n+1)+6+12=12n+30.$ Therefore, by Proposition 3.1 we conclude $$\text{GP}(F_n)=\frac{12n+30}{2}\left(43+58+36(n-1)\right)=216n^2+930n+975.$$

We observe that the Graovac-Pisanski index of fullerene F_n is an integer number for any $n\ge 1.$ Also, the Graovac-Pisanski index of two other families of nanotubical fullerenes was computed in^[18] and the result is again an integer number, what coincides with Proposition 4.2.

5. Graphs for which the Graovac-Pisanski index is not an integer

By Theorem 3.4, Corollary 3.2, and Proposition 4.2, many chemical graphs have integer Graovac-Pisanski index (for example the fullerene graphs, trees, hexagonal structures, etc.). Of course, there are also connected graphs whose Graovac-Pisanski index is not an integer. The smallest such graph contains 5 vertices.

In Table 1 we present the number of connected graphs on n vertices, $n\in \{3,5,7,9\},$ whose Graovac-Pisanski index is not an integer number. The results were obtained by using a computer programme.

Table 1. Number of connected graphs on 3, 5, 7, and 9 vertices, divided in those with an integer and those with a non-integer Graovac-Pisanski index.

Number of vertices	3	5	7	9
Number of connected graphs	2	21	853	261080
Number of graphs whose GP index is integer	2	14	516	197584
Number of graphs whose GP index is not integer	0	7	337	18496

In Figure 5 we can see all the connected graphs on 5 vertices whose Graovac-Pisanski index is not an integer number.

Figure 5. All connected graphs on 5 vertices for which the Graovac-Pisanski index is not an integer.

The following theorem presents an infinite class of unicyclic graphs for which the Graovac-Pisanski index is not an integer number.

Theorem 5.1.

Let G be a graph consisting of a cycle of odd length ℓ, where $\mathcal{\ell }\equiv 3\mathrm{ }\text{or}\mathrm{ }5\hspace{1em}(\mathrm{mod} 8)$, to which we attach a path of even length t, where t is a positive integer. Then G has $\mathcal{\ell }+t$ vertices and $\text{GP}(G)$ is not an integer number.

Proof.

In G there are $\frac{\mathcal{\ell }-1}{2}$ orbits with two vertices and t + 1 orbits with one vertex. Let z be the vertex of degree 3 in G. Then the orbits with two vertices contain pairs of vertices at the same distance from z. Hence, the distances between the pairs of vertices from the same orbit are $1,2,\dots ,\frac{\mathcal{\ell }-1}{2}$ and $$\text{GP}(G)=|V(G)|·\frac{1}{2}·(1+2+\dots +\frac{\mathcal{\ell }-1}{2})=|V(G)|·\frac{1}{2}·\left(\begin{array}{c}(\mathcal{\ell }+1)/2\\ 2\end{array}\right).$$

It is easy to observe that the number $|V(G)|=\mathcal{\ell }+t$ is odd and consequently, the Graovac-Pisanski index is not an integer if and only if the number representing the binomial coefficient, $\frac{1}{2}\frac{\mathcal{\ell }+1}{2}\frac{\mathcal{\ell }-1}{2},$ is odd. □

An example of a graph satisfying assumptions of Theorem 5.1 is presented as the last graph in Figure 5.

Finally, we also remark that if G is a dual of a fullerene, then $\text{GP}(G)$ can be an integer number or not an integer number, what is apparent from the results in.^[18]

Additional information

Funding

The author Matevž Črepnjak acknowledges the financial support from the Slovenian Research Agency, research core funding No. P1-0403. The author Martin Knor acknowledges partial support by Slovak research grants VEGA 1/0142/17, VEGA 1/0238/19, APVV-15-0220 and APVV-17-0428 and Slovenian research agency ARRS, program no. P1-0383. The authors Niko Tratnik and Petra Žigert Pleteršek acknowledge the financial support from the Slovenian Research Agency, research core funding No. P1-0297 and J1-9109.