# Gutman Index and Detour Gutman Index of Pseudo-Regular Graphs

Authors: S. Kavithaa; V. Kaladevi
Journal: Journal of Applied Mathematics
 (2017)

---

## Abstract

The Gutman index of a connected graphG is defined as Gut(G)=∑u≠vd(u)d(v)d(u,v), where d(u)  and  d(v) are the degree of the vertices u  and  v and d(u,v) is the distance between vertices u  and  v. The Detour Gutman index of a connected graph G is defined as GutG=∑u≠vd(u)d(v)D(u,v), where D(u,v) is the longest distance between vertices u  and  v. In this paper, the Gutman index and the Detour Gutman index of pseudo-regular graphs are determined.


---

## Body

## 1. Introduction

All graphs considered in this paper are simple, connected, and finite. A graph is a collection of points and lines connecting a subset of them. The points and lines of a graphG are also called vertices and edges of the graph and are denoted by V(G)  and  E(G), respectively. For u,v∈V(G), the distance between u  and  v in G, denoted by d(u,v), is the length of the shortest (u,v)-path in G. The number of vertices of G adjacent to a given vertex v is the degree of this vertex and it is denoted by d(v).A topological index is a real number related to a graph. It does not depend on the labeling or pictorial representation of a graph. The Wiener index ofG, W(G) is defined as W(G)=∑u≠vd(u,v), where the sum is taken through all unordered pairs of vertices of G. Wiener index was introduced by Wiener, as an aid to determine the boiling point of Paraffin [1]. It is related to boiling point, heat of evaporation, heat of formation, chromatographic relation times, surface tension, vapour pressure, partition coefficients, total electron energy of polymers, ultrasonic sound velocity, internal energy, and so on [2]. For this reason, Wiener index is widely studied by chemists.In [3], Gutman defined the modified Schultz index, which is known as the Gutman index as a kind of a vertex-valency-weighted sum of the distance between all pair of vertices in a graph. Gutman revealed that, in the case of acyclic structures, the index is closely related to the Wiener index and reflects precisely the same structured features of a molecular as the Wiener index does.The Gutman index of G, denoted byGut(G), is defined as Gut(G)=∑{u,v}⊆V(G)dGudGvdGu,v=1/2∑u,v∈V(G)dGudGvdGu,v with the summation runs over all pair of vertices of G. Dankelmann et al. [4] presented an upper bound for the Gutman index and also established the relation between the Edge-Wiener index and Gutman index of graphs. Chen and Liu [5] studied the maximal and minimal Gutman index of unicyclic graphs, and they also determined the minimal Gutman index of bicyclic graphs [6].IfG is a tree on n vertices, then Wiener index and Gutman index are closely related by Gut(G)=4W(G)-2n-1n-1. For path graph Pn, W(Pn)=n(n2-1)/6, and for star graph Sn, W(Sn)=(n-1)2. Thus, GutPn=n-12n2-4n+3/3 and Gut(Sn)=2n-3n-1. Also, for every tree Tn of order n, Gut(Sn)≤Gut(Tn)≤Gut(Pn).For any acyclic connected graph, the shortest distanced(u,v) is the same as the longest distance D(u,v). But for cyclic structured graphs, the shortest distance d(u,v) naturally is not equal to the longest distance D(u,v). In this paper, the new index which is Gutman index of graphs with respect to detour distance [7, 8] is considered; this is named as Detour Gutman index which is defined as DGut(G)=∑u≠vd(u)d(v)D(u,v).A graphG is called pseudo-regular graph [9, 10] if every vertex of G has equal average degree. The main goal of this paper is to find the exact formula for Gutman index and Detour Gutman index of pseudo-regular graphs.


## 2. Pseudo-Regular Graphs

LetG=(V,E) be a simple, connected, undirected graph with n vertices and m edges. For any vertex vi∈V, the degree of vi is the number of edges incident on vi. It is denoted by di or d(vi). A graph G is called regular if every vertex of G has equal degree. A bipartite graph is called semiregular if each vertex in the same part of a bipartition has the same degree. The 2-degree vi [9] is the sum of the degree of the vertices adjacent to vi and denoted by ti [11]. The average degree of vi is defined as ti/di. For any vertex vi∈V, the average degree of vi is also denoted by mvi=ti/di.A graphG is called pseudo-regular graph [9] if every vertex of G has equal average degree and mG=1/n∑v∈VGm(u) is the average neighbor degree number of the graph G.A graph is said to ber-regular if all its vertices are of equal degree r. Every regular graph is a pseudo-regular graph [10]. But the pseudo-regular graph need not be a regular graph. Pseudo-regular graph is shown in Figures 1 and 2.Figure 1Figure 2In Figure1, there are 14 vertices of degree 1, 7 vertices of degree 3, and 1 vertex of degree 7. So totally there are 22 vertices in the graph. Average degree of vertices of degree 1 is equal to 3/1 = 3. Average degree of vertices of degree 2 is equal to 9/3 = 3. Average degree of vertices of degree 7 is equal to 21/7 = 3. Therefore, average degree of each vertex is 3. Hence, it is a pseudo-regular graph. In Figure 2, average degree of each vertex is 5. Hence, the graph in Figure 2 is also a pseudo-regular graph.The relevance of pseudo-regular graph for the theory of nanomolecules and nanostructure should become evident from the following. There exist polyhedral (planar, 3-connected) graphs and infinite periodic planar graphs belonging to the family of the pseudo-regular graphs. Among polyhedral, the deltoidal hexecontahedron possesses pseudo-regular property. The deltoidal hexecontahedron is a Catalan polyhedron with 60 deltoid faces, 120 edges, and 62 vertices with degrees 3, 4, and 5, and average degree of its vertices is 4.In this paper, the Gutman index and Detour Gutman index for three types of pseudo-regular graphs are derived. For construction of pseudo-regular graphs, see [12].


## 3. Gutman Index and Detour Gutman Index of Type I Pseudo-Regular Graph

Theorem 1.
Forp≥2, the Gutman index of type I pseudo-regular graph GI is(1)GutGI=2p7+42p6-275p5+3006p4-18889p3+54808p2-74014p+380402p.Proof.
LetG=GI be the type I pseudo-regular graph.
LetV(G)=v0,v1,v2,…,vm,u1,u2,…,ump-1 be the vertex set of G and let v0 be the central vertex of star graph K1,m, v1,v2,…,vm are pendant vertices of K1,m, where m=p2-p+1, and the (p-1) pendant vertices u1,u2,…,ump-1 are attached with m pendant vertices v1,v2,…,vm.
LetE(G)=v0vi;1≤i≤m∪{v1uj;1≤j≤p-1}∪{v2uj;p≤j≤2p-2}∪v3uj;2p-1≤j≤3p-3∪⋯vmuj;m-1p-m+2≤j≤mp-m. The pseudo-regular graph of type I for p=3 is shown in Figure 3.
The Gutman index of any graphG is given by Gut(G)=∑u≠vdudvdu,v.
Now(2)GutGI=∑i=1mdv0dvidv0,vi+∑i=1m∑j=i+1mdvidvjdvi,vj+∑i=1mp-1dv0duidv0,ui+∑i=1m∑j=1mp-1dvidujdvi,uj+∑1≤i<j≤nduidujdui,uj=GutK1,m+∑i=1mp-1dv0duidv0,ui+∑i=1m∑j=1mp-1dvidujdvi,uj+∑1≤i<j≤nduidujdui,uj=p6+p5-13p4+25p3-15p2+3p+8+2p5-6p4+10p3-10p2+6p-2+1141p4-896p3+27083p2-36931p+19020p+36p5-237p4+654p3-913p2+624p-1642,GutGI=2p7+42p6-275p5+3006p4-18889p3+54808p2-74014p+380402p.Figure 3
Pseudo-regular graph of type I atp=3.


## 4. Gutman Index and Detour Gutman Index of Type II Pseudo-Regular Graph

Theorem 2.
Forp≥3, the Gutman index of type II Pseudo-regular graph GII is (3)GutGII=3p9-93p8+1181p7-8026p6+32047p5-75192p4+87593p3+8025p2-145324p+1213142p-1.Proof.
LetG=GII be a type II pseudo-regular graph.
LetV(G)=v0,v1,v2,…,vm,u1,u2,…,ump-3 be the vertex set of G and v0 as the central vertex of wheel graph Wm and v1,v2,…,vm are vertices of cycle cm in the clockwise direction and u1,u2,…,ump-3 are the pendant vertices joined to every vertex in the cycle except the central vertex, where m=p2-3p+3.
LetEG=v0vi;1≤i≤m∪vivi+1;1≤i≤m-1∪vmv1∪{v1uj;1≤j≤p-3}∪v2uj;p-2≤j≤2(p-3)∪⋯vmuj;m≤j≤mp-3. The pseudo-regular graph of type II for p=5 is shown in Figure 4.
The Gutman index ofG is given by Gut(G)=∑u≠vd(u)d(v)d(u,v).
Now(4)GutGII=∑i=1mdv0,vidv0dvi+∑i=1m∑j=i+1mdvidvjdvi,vj+∑i=1mp-3dv0duidv0,ui+∑i=1m∑j=1mp-3dvidujdvi,uj+∑1≤i<j≤mp-3duidujdui,uj=GutK1+Cm+∑i=1mp-3dv0duidv0,ui+∑i=1m∑j=1mp-3dvidujdvi,uj+∑1≤i<j≤mp-3duidujdui,uj=-10p6+393p5-3650p4+14717p3-27872p2+20382p2p-1+12p5-148p4+671p3-1292p2+759p+306+3p9-93p8+1173p7-7920p6+31232p5-70772p4+72458p3+36097p2-167010p+1224002p-1+4p6-56p5+315p4-88p3+1283p2-868p+237,GutGII=3p9-93p8+1181p7-8026p6+32047p5-75192p4+87593p3+8025p2-145324p+1213142p-1.Figure 4
Pseudo-regular graph of type II atp=5.Theorem 3.
Forp≥3, the Detour Gutman index of type II pseudo-regular graph GII is (5)DGutGII=3p13-150p12+3267p11-40822p10+324929p9-1730282p8+6302777p7-15784266p6+26967288p5-31025576p4+24249128p3-14093944p2+6618144p-166147216p-1p-2.Proof.
LetG=GII be a type II pseudo-regular graph.
LetV(G)=v0,v1,v2,…,vm,u1,u2,…,ump-3 be the vertex set of G and v0 as the central vertex of wheel graph Wm and {v1,v2,…,vm} are vertices of cycle cm in the clockwise direction and u1,u2,…,ump-3 are the pendant vertices joined to every vertex in the cycle except the central vertex, where m=p2-3p+3.
LetEG=v0vi;1≤i≤m∪vivi+1;1≤i≤m-1∪vmv1∪{v1uj;1≤j≤p-3}∪v2uj;p-2≤j≤2(p-3)∪⋯vmuj;m≤j≤mp-3.
The Detour Gutman index ofG is given by DGut(G)=∑u≠vd(u)d(v)D(u,v).
Now(6)DGutGII=∑i=1mDv0,vidv0dvi+∑i=1m∑j=i+1mdvidvjDvi,vj+∑i=1mp-3dv0duiDv0,ui+∑i=1m∑j=1mp-3dvidujDvi,uj+∑1≤i<j≤mp-3duidujDui,uj=DGutK1+Cm+∑i=1mp-3dv0duiDv0,ui+∑i=1m∑j=1mp-3dvidujDvi,uj+∑1≤i<j≤mp-3duidujDui,uj=3p12-147p11+3120p10-37710p9+287235p8-1441911p7+4846138p6-10839136p5+15691368p4-14003680p3+16p-2+7515504p2-3133728p+130636816p-2+42p5-539p4+2912p3-8407p2+13020p-8568+2p10-46p9+490p8-3020p7+11314p6-24572p5+22173p4+22916p3-75151p2+53958pp-1p-2+-6p8+162p7-1746p6+10032p5-33756p4+67700p3-77828p2+45678p-101164,DGutGII=3p13-150p12+3267p11-40822p10+324929p9-1730282p8+6302777p7-15784266p6+26967288p5-31025576p4+24249128p3-14093944p2+6618144p-166147216p-1p-2-1.


## 5. Gutman Index of Pseudo-Regular Graph of Type III

Theorem 4.
Forp≥5, the Gutman index of type III pseudo-regular graph GIII is(7)GutGIII=9p8-237p7+2670p6-16723p5+63422p4-148307p3+207979p2-161586p+55987.Proof.
LetG=GIII be a type III pseudo-regular graph.
LetVG={v0,v1, v2,…,vm, u1, u2,…,ump-5, w1,w2,…,wm} be the vertex set of G and v0 as the central vertex of wheel graph wm, where m=p2-3p+1.
LetEG=v0vi;1≤i≤m∪vivi+1;1≤i≤m-1∪vmv1;1≤j≤mp-5∪u1vi;1≤i≤2∪u2vi;2≤i≤3,…,umvi;m-1≤i≤m∪viwj;1≤j≤p-5∪v2wj;p-4≤j≤2p-5∪vmwj;m≤j≤mp-5. The pseudo-regular graph of type III for p=6 is shown in Figure 5.
The Gutman index ofG is given by GutG=∑u≠vdudvdu,v.
Now(8)GutGIII=∑i=1mdv0dvidv0,vi+∑i=1m∑j=i+1mdvidvjdvi,vj+∑i=1mp-5dv0dwidv0,wi+∑i=1mdv0duidv0,ui+∑i=1m∑j=1mp-5dvidwjdvi,wj+∑i=1m∑j=1mdvidujdvi,uj+∑i=1mp-5∑j=1mp-5dwidwjdwi,wj+∑i=1mp-5∑j=1mdwidujdwi,uj+∑i=1m∑j=1mp-5duidwjdui,wj+∑i=1m∑j=1mduidujdui,ujGutGIII=GutK1+Cm+∑i=1mp-5dv0dwidv0,wi+∑i=1mdv0duidv0,ui+∑i=1m∑j=1mp-5dvidwjdvi,wj+∑i=1m∑j=1mdvidujdvi,uj+∑i=1mp-5∑j=1mp-5dwidwjdwi,wj+∑i=1mp-5∑j=1mdwidujdwi,uj+∑i=1m∑j=1mp-5duidwjdui,wj+∑i=1m∑j=1mduidujdui,ujGutGIII=9p5-59p4+91p3+18p2+p+2p6-32p5+192p4-532p3+672p2-320p+50+4p4-24p3+44p2-24p+4+6p5-36p4+54p3-6p+17p5-288p4+1823p3-5197p2+6120p-1675+4p8-112p7+1352p6-9171p5+38131p4-99177p3+156993p2-137780p+51200+372p2-2332p+3108.GutGIII=9p8-237p7+2670p6-16723p5+63422p4-148307p3+207979p2-161586p+55987.Figure 5
Pseudo-regular graph of type III atp=6.Theorem 5.
Forp≥5, the Detour Gutman index of type III pseudo-regular graph GIII is(9)DGutGIII=2p12-66p11+834p10-3163p9-42773p8+740044p7-5734272p6+28024578p5-92778639p4+209280657p3-309883869p2+272578823p-108183686.Proof.
LetG=GIII be a type III pseudo-regular graph.
LetVG={v0,v1, v2,…,vm, u1, u2,…,ump-5, w1,w2,…,wm} be the vertex set of G and v0 as the central vertex of wheel graph wm, where m=p2-3p+1 and {u1,u2,…,ump-5} are the pendant vertices and {w1,w2,…,wm} are the vertices joined to the end vertices of each edge of a wheel graph except the central vertex.
LetEG=v0vi;1≤i≤m∪vivi+1;1≤i≤m-1∪vmv1;1≤j≤mp-5∪u1vi;1≤i≤2∪u2vi;2≤i≤32,…,umvi;m-1≤i≤m∪viwj;1≤j≤p-5∪v2wj;p-4≤j≤2p-5∪vmwj;m≤j≤mp-5.
The Detour Gutman index ofG is given by DGut(G)=∑u≠vd(u)d(v)D(u,v).
Now(10)DGutGIII=∑i=1mdv0dviDv0,vi+∑i=1m∑j=i+1mdvidvjDvi,vj+∑i=1mp-5dv0dwiDv0,wi+∑i=1mdv0duiDv0,ui+∑i=1m∑j=1mp-5dvidwjDvi,wj+∑i=1m∑j=1mdvidujDvi,uj+∑i=1mp-5∑j=1mp-5dwidwjDwi,wj+∑i=1mp-5∑j=1mdwidujDwi,uj+∑i=1m∑j=1mp-5duidwjDui,wj+∑i=1m∑j=1mduidujDui,ujDGutGIII=DGutK1+Cm+∑i=1mp-5dv0dwiDv0,wi+∑i=1mdv0duiDv0,ui+∑i=1m∑j=1mp-5dvidwjDvi,wj+∑i=1m∑j=1mdvidujDvi,uj+∑i=1mp-5∑j=1mp-5dwidwjDwi,wj+∑i=1mp-5∑j=1mdwidujDwi,uj+∑i=1m∑j=1mp-5duidwjDui,wj+∑i=1m∑j=1mduidujDui,ujDGutGIII=8p10-200p9+1912p8-6812p7-20084p6+305108p5-1363182p4+3178959p3-3854871p2+1778689p+261036+18p11-826p10+17250p9-216444p8+1813319p7-10651871p6+44774333p5-134688490p4+284180079p3-400550125p2+339452825p-131036500+8p9-248p8+3384p7-26584p6+131820p5-424452p4+875734p3-1089150p2+701402p-149768+2p12-84p11+1652p10-20230p9+172232p8-1072340p7+4980735p6-17261562p5+43954031p4-79624939p3+96831776p2-70644085p+23295900+9p9-225p8+2421p7-14604p6+53841p5-123786p4+172950p3-135549p2+50376p-6864+162p5-2736p4+17262p3-49050p2+57600p-15750+[72p7-1864p6+20812p5-129160p4+476036p3-1025500p2+1169800p-528500+64p5-864p4+4576p3-11400p2+12216p-3240,DGutGIII=2p12-66p11+834p10-3163p9-42773p8+740044p7-5734272p6+28024578p5-92778639p4+209280657p3-309883869p2+272578823p-108183686.


## 6. Conclusion

In this paper, we clearly determined the Gutman index of pseudo-regular graphs and also determined the Detour Gutman index of pseudo-regular graphs.



---

*Source: 4180650-2017-08-15.xml*