Article Search
eISSN 0454-8124
pISSN 1225-6951

### Article

Kyungpook Mathematical Journal 2020; 60(3): 467-475

Published online September 30, 2020

### On Diameter, Cyclomatic Number and Inverse Degree of Chemical Graphs

Reza Sharafdini*, Ali Ghalavand and Ali Reza Ashrafi

Department of Mathematics, Faculty of Science, Persian Gulf University, Bushehr 75169-13817, Iran
e-mail : sharafdini@pgu.ac.ir
Department of Pure Mathematics, Faculty of Mathematical Science, University of Kashan, Kashan 87317-53153, Iran

Received: June 20, 2019; Revised: April 21, 2020; Accepted: April 22, 2020

Let G be a chemical graph with vertex set {v1, v1, … , vn} and degree sequence d(G) = (degG(v1), degG(v2), … , degG(vn)). The inverse degree, R(G) of G is defined as $R(G)=∑i=1n1degG(vi)$. The cyclomatic number of G is defined as γ = mn + k, where m, n and k are the number of edges, vertices and components of G, respectively. In this paper, some upper bounds on the diameter of a chemical graph in terms of its inverse degree are given. We also obtain an ordering of connected chemical graphs with respect to the inverse degree.

Keywords: diameter, cyclomatic number, pendant vertex, inverse degree, chemical graph

Throughout this paper, all graphs are assumed to be undirected, simple and connected. Let G be such a graph. We denote its vertex set and edge set by V (G) and E(G), respectively. The degree of a vertex v, degG(v), is defined as the size of {wV (G) | vwE(G)}. A vertex of degree one is called a pendant vertex.

The number of vertices of degree i in G is denoted by ni = ni(G). Obviously ∑i≥1ni = |V (G)|. A chemical graph is a graph with a maximum degree of less than or equal to 4. This reflects the fact that chemical graphs represent the structure of organic molecules– carbon atoms being 4-valent and double bonds being counted as single edges.

The distance dG(u, v) between two vertices u and v of G is the length of a shortest uv path in G, and the diameter is defined as diam(G) = max{dG(u, v) | u, vV (G)}.

The cyclomatic number of a connected graph G is the minimum number of edges that must be removed from the graph to break all its cycles, making it into a tree or forest. The cyclomatic number γ(G) can be expressed as γ(G) = mn + k, where n, m and k denote the number of vertices, edges and components of G, respectively.

A graph with cyclomatic number 0, 1, 2, 3, 4 or 5 is said to be a tree, unicyclic, bicyclic, tricyclic, tetracyclic or pentacyclic, respectively. Suppose E′ is a subset of E(G). The subgraph GE′ of G is obtained by deleting the edges of E′. If uvE(G), then the graph G + uv obtained from G by attaching vertices u, v.

Suppose r = (r1, r2, … , rn) and s = (s1, s2, … , sn) are two non-increasing vectors in ℝn. If $∑i=1kri≤∑i=1ksi$, 1 ≤ kn−1, and $∑i=1nri≤∑i=1nsi$, then we say that r is majorized by s, and we write rs. Moreover, rs means that rs and rs, see [10] for details. The non-increasing sequence d = (d1, d2, … , dn) of nonnegative integers is called a graphic sequence if we can find a simple graph G with the vertex set V (G) = {v1, v2, … , vn} such that di = degG(vi), 1 ≤ in. The inverse degree, R(G) of G was defined as $R(G)=∑i=1n1degG(vi)$, under the name zeroth-order Randić index by Kier and Hall in [9]. The inverse degree attracted attention through conjectures of the computer program Graffiti [6]. Since then its relationship with other graph invariants, such as diameter, edge-connectivity, matching number, chromatic number, clique number, Wiener index, GA1-index, ABC-index and Kf-index has been studied by several authors (see, for example, [1, 2, 4, 5, 12]). Some extremal graphs with respect to the inverse degree are given (see, for example, [11]).

In this paper, some upper bounds on the diameter of a chemical graph in terms of its inverse degree are given. We also obtain an ordering of connected chemical graphs with respect to inverse degree.

### 2. Bounds on the Inverse Degree

In this section, some new bounds for inverse degree are presented. We start this section with the following lemma:

### Lemma 2.1.([8])

If G is a connected graph with n vertices and cyclomatic number γ, then$n1(G)=2-2γ+∑i=3Δ(G)(i-2)ni$and$n2(G)=2γ+n-2-∑i=3Δ(G)(i-1)ni$.

### Proposition 2.2

Let G be a connected graph with m edges.

• (1) If GPn, then γ(G) = m − diam(G) − n1 + 2.

• (2) If GPn, then γ(G) ≤ m − diam(G) − n1 + 1.

Proof

It is clear that γ(Pn) = m−diam(G)−n1+2. Let G be a graph such that GPn. Suppose u, vV (G), dG(u, v) = diam(G) and uw1w2wdiam(G)−1v is a shortest uv path in G. Let A = {uw1, w1w2, … , wdiam(G)−2wdiam(G)−1, wdiam(G)−1v} and B = {uv | uvE(G) and uv is a pendant edge in G }. Then observe that |AB| ≤ 2 and the subgraph G − (E \ (AB ∪ {e})) is an acyclic graph, where eE \ (AB). Therefore, γ(G) ≤ m − diam(G) − n1 + 1.

### Corollary 2.3

Let G be a connected graph with n vertices and m edges except Pn. Then diam(G) ≤ nn1 + 1. Furthermore, if G is a chemical graph, then$diam(G)≤2n-γ(G)-52n1+1$.

Proof

By Proposition 2.2, we have diam(G) ≤ nn1+1 since γ(G) = mn+1. It is well-known that for a chemical graph G, $m≤2n-32n1$. Therefore, by Proposition 2.2, $diam(G)≤2n-γ(G)-52n1+1$.

### Theorem 2.4

Let G be a connected chemical graph with n vertices, m edges and cyclomatic number γ.

• (1) If GPn, then diam(G) = 2R(G) − n1 − 1.

• (2) If GPn, then diam(G) ≤ 4R(G) − n1.

Proof

It is easy to see that diam(Pn) = 2R(G)−n1 −1. For GPn, by definition of R(G) and Lemma 2.1,

$R(G)=2-2γ+12n2+43n3+94n4.$

By Proposition 2.2, and the fact that $m=12(n1+2n2+3n2+4n4)$, we have

$R(G)≥n1-32n2-53n3-74n4+2 diam(G)=2n1-(n1+32n2+53n3+74n4)+2 diam(G)≥2n1-7(n1+12n2+13n3+14n4)+2 diam(G).$

Thus diam(G) ≤ 4R(G) − n1.

### Corollary 2.5

Let G be a connected chemical graph with n vertices and m edges. Then$R(G)=32n-m+13n3+34n4$. Besides, if n4 = 0, diam(G) ≤ 3R(G) − n1.

Proof

By definition,

$R(G)=∑v∈V(G)1degG(v)=n1+n22+n33+n44=112(12n1+6n2+4n3+3n4).$

Now, by Lemma 2.1. and γ(G) = mn+1, we have $R(G)=32n-m+13n3+34n4$. If n4 = 0, then by Eq. (2.1), $R(G)≥2n1-(n1+32n2+53n3)+2 diam(G)$. Therefore, diam(G) ≤ 3R(G) − n1.

### Corollary 2.6

Let G be a connected chemical graph with n vertices and m edges. Then$R(G)≥32n-m$, with equality if and only if GPnor Cn.

### Corollary 2.7

Let G be a connected chemical graph with n vertices. Then the following hold:

• (1) If G is a tree, then$R(G)≥12n+1$, with equality if and only if GPn.

• (2) If G is unicyclic, then$R(G)≥12n$, with equality if and only if GCn.

For n ≥ 5 we set

$Γ1={B∣B is a bicyclic graph, n3(B)=2 and n2(B)=n-2},Γ2={B∣B is a bicyclic graph, n4(B)=1 and n2(B)=n-1}.$

### Corollary 2.8

Let G be a chemical bicyclic graph with n ≥ 5 vertices. If B1 ∈ Γ1, B2 ∈ Γ2and G ∉ Γ1 ∪ Γ2, then$R(B1).

Proof

By Corollary 2.5, if n4(G) ≥ 1, then $R(G)≥12n-14$, with equality if and only if G ∈ Γ2. If n4(G) = 0 and n3(G) = 0 or n4(G) = 0 and n3(G) = 1, then G is not a chemical bicyclic graph. If n4(G) = 0 and n3(G) = 2, then $R(G)=12n-13$; and if n4(G) = 0 and n3(G) ≥ 3, then $R(G)≥12n$, proving the corollary.

For n ≥ 5 we set

$Λ1={G∣G is a tricyclic graph, n3(G)=4 and n2(G)=n-4},Λ2={G∣G is a tricyclic graph, n4(G)=1, n3(G)=2 and n2(G)=n-3}.$

### Corollary 2.9

Let G be a chemical tricyclic graph with n ≥ 5 vertices. If G1 ∈ Λ1, G2 ∈ Λ2and G ∉ Λ1 ∪ Λ2, then$R(G1).

Proof

By Corollary 2.5, if n4(G) ≥ 2, $R(G)≥12n+12$. If n4(G) = 1 and n3(G) ≤ 1, or n4(G) = 0 and n3(G) ≤ 3, then G is not a chemical tricyclic graph. If n4(G) = 0 and n3(G) = 4, then $R(G)=12n+13$. If n4(G) = 1 and n3(G) = 2, then $R(G)=12n+512$. If n4(G) = 0 and n3(G) ≥ 5, then $R(G)≥12n+23$. If n4(G) = 1 and n3(G) ≥ 3, then $R(G)=12n+34$, proving the result.

The proofs of the following two corollaries are similar to that of Corollary 2.8 and Corollary 2.9. So we omit them.

Next we define the following two sets, when n ≥ 6,

$Θ1={G∣G is a tetracyclic graph, n3(G)=6 and n2(G)=n-6},Θ2={G∣G is a tetracyclic graph, n4(G)=1, n3(G)=4 and n2(G)=n-5}.$

### Corollary 2.10

Let G be a chemical tetracyclic graph with n ≥ 6 vertices. If G1 ∈ Θ1and G2 ∈ Θ2and G ∉ Θ1 ∪ Θ2, then$R(G1).

For n ≥ 8 we define

$ϒ1={G∣G is a pentacyclic graph, n3(G)=8 and n2(G)=n-8},ϒ2={G∣G is a pentacyclic graph, n4(G)=1, n3(G)=6 and n2(G)=n-7}.$

### Corollary 2.11

Let G be a chemical pentacyclic graph with n ≥ 6 vertices. If G1 ∈ ϒ1, G2 ∈ ϒ2and G ∉ ϒ1 ∪ ϒ2, then$R(G1).

### 3. Ordering Chemical Trees and Unicyclic Graphs with Respect to the Inverse Degree Index

Recall that if I ⊂ ℝ is an interval and f : I → ℝ is a real-valued function such that f″(x) ≥ 0 on I, then f is convex on I. If f″(x) > 0, then f is strictly convex on I. A real-valued function ϕ defined on a set Λ ⊂ ℝn is said to be Schurconvex on Λ if for all x = (x1, … , xn) and y = (y1 … , yn) ∈ Λ, if xy, then ϕ(x) ≤ ϕ(y). In addition, ϕ is said to be strictly Schur-convex on Λ if xy implies that ϕ(x) < ϕ(y).

### Lemma 3.1.([10])

Let I ⊂ ℝ be an interval and let$ϕ(x1,…,xn)=∑i=1ng(xi)$, where g : I → ℝ. If g is strictly convex on I, then ϕ is strictly Schur-convex on In.

### Theorem 3.2

Let G and Gbe two connected graphs with the degree sequences d(G) = (d1, … , dn) and$d(G′)=(d1′,…,dn′)$, respectively. If d(G) ⪯ d(G′), then R(G) ≤ R(G′), with equality if and only if d(G) = d(G′).

Proof

Let α : (0,∞) → ℝ be a real-valued function such that $α(x)=1x$ for all x ∈ (0,∞). Then observe that for x > 0, $α″(x)=2x3>0$. Therefore, α is strictly convex on (0,∞). So by Lemma 3.1, inverse degree, R, is strictly Schur-convex. Thus R(G) ≤ R(G′), with equality if and only if d(G) = d(G′).

### Lemma 3.3

(See [7]) Suppose that G1is a graph with given vertices v1and v2, such that degG1 (v1) ≥ 2 and degG1 (v2) = 1. In addition, assume that G2is another graph and w is a vertex in G2. Let G be the graph obtained from G1and G2by attaching vertices w and v1. If G′ = Gwv1 + wv2, then d(G′) ≺ d(G).

### Theorem 3.4

Among all graphs with n vertices and cyclomtatic number γ (1 ≤ γn − 2), a graph$Gγ1$with the degree sequence

$d(Gγ1)=(n-1,γ+1,2,…,2︸γ,1,…,1︸n-γ-2)$

has the maximal inverse degree and a graph$Gγ2$with the degree sequence

$d(Gγ2)=(x+1,…,x+1︸y,x,…,x︸n-y),$

where$x=⌊2n+2γ-2n⌋$and y ≡ 2n+2γ−2 (mod n), has the minimal inverse degree.

Proof

Let G be an arbitrary simple connected graph with n vertices and with cyclomtatic number γ (1 ≤ γn−2) which is different from $Gγ1$ and $Gγ2$. Dimitrov and Ali in [3] showed that $d(Gγ2)≺d(G)≺d(Gγ1)$. Now, the result follows from Theorem 3.2.

### Theorem 3.5

Let TiAi, for 1 ≤ i ≤ 31 (SeeTable 1). If n ≥ 22 and T is a tree such that$T∉∪i=131Ai$, then R(Ti) < R(Ti+1) for i ∈ {1, 2, … , 29}\ {25}, R(T25) = R(T26), R(T30) = R(T31) and R(T31) < R(T).

Proof

By data given in the Table 1, and simple calculations one can see that, R(Ti) < R(Ti+1) for i ∈ {1, 2, … , 29}\{25}, R(T25) = R(T26), R(T30) = R(T31) and R(T31) < R(T) for $T∈∪i=3236Ai$. If n1(T) > 12, then by the repeated application of Lemma 3.3 on the vertices of degree 1, we arrive at a tree Tl, in which R(Tl) < R(T) and n1(Tl) = 12. Now, by Lemma 2.1 and simple calculations one can see that, T is a chemical tree of order n with 2 ≤ n1(T) ≤ 12 if and only if T is given in Table 1. Therefore, by Table 1, R(T31) ≤ R(Tl) < R(T) and this completes the proof.

### Theorem 3.6

Let UiBi, for 1 ≤ i ≤ 41 and U42B43(See Table 2). If n ≥ 24 and U is a chemical unicyclic graph such that$U∉∪i=141Bi∪B43$, then for i ∈ {1, 2, … , 40}\ {25, 30, 36}, R(Ui) < R(Ui+1)

$R(U25)=R(U26),R(U30)=R(U31),R(U35)=R(U37),R(U36)=R(U38),R(U41)=R(U42),$

and R(U42) < R(U).

Proof

By Table 2, we can see that, for i ∈ {1, 2, … , 40}\ {25, 30, 36}, R(Ui) < R(Ui+1) and

$R(U25)=R(U26),R(U30)=R(U31),R(U35)=R(U37),R(U36)=R(U38),R(U41)=R(U42)$

and R(U42) < R(U) for $U∈∪i=4349Bi$.

If n1(U) > 12, then by the repeated application of Lemma 3.3 on the vertices of degree 1 we arrive at a unicyclic graph Ul, in which R(Ul) < R(U) and n1(Ul) = 12. Now, by Lemma 2.1 and simple calculations one can see that, U is a chemical unicyclic graph of order n with 2 ≤ n1(U) ≤ 12 if and only if U is given in Table 2. Therefore, by Table 2, R(U42) ≤ R(Ul) < R(U) and this completes the proof.

The research of the second and the third authors was partially supported by the University of Kashan under grant no 364988/180.

1. X. Chen, and S. Fujita. On diameter and inverse degree of chemical graphs. Appl Anal Discrete Math., 7(2013), 83-93.
2. KC. Das, K. Xu, and J. Wang. On inverse degree and topological indices of graphs. Filomat., 30(8)(2016), 2111-2120.
3. D. Dimitrov, and A. Ali. On the extremal graphs with respect to variable sum exdeg index. Discrete Math Lett., 1(2019), 42-48.
4. R. Entringer. Bounds for the average distance-inverse degree product in trees. Combinatorics, Graph Theory, and Algorithms, I, II, New Issues Press, Kalamazoo, MI, 1999:335-352.
5. P. Erdös, J. Pach, and J. Spencer. On the mean distance between points of a graph. Congr Numer., 64(1988), 121-124.
6. S. Fajtlowicz. On conjectures of graffiti II. Congr Numer., 60(1987), 189-197.
7. A. Ghalavand, and AR. Ashrafi. Extremal graphs with respect to variable sum exdeg index via majorization. Appl Math Comput., 303(2017), 19-23.
8. A. Ghalavand, AR. Ashrafi, and I. Gutman. Extremal graphs for the second multiplicative Zagreb index. Bull Int Math Virtual Inst., 8(2)(2018), 369-383.
9. LB. Kier, and LH. Hall. The nature of structure-activity relationships and their relation to molecular connectivity. European J Med Chem., 12(1977), 307-312.
10. AW. Marshall, and I. Olkin. Inequalities: Theory of majorization and its applications. Mathematics in Science and Engineering, 143, Academic Press, Inc, New York-London, 1979.
11. K. Xu, . Kexiang, and K. Ch Das. Some extremal graphs with respect to inverse degree. Discrete Appl Math., 203(2016), 171-183.
12. Z. Zhang, J. Zhang, and X. Lu. The relation of matching with inverse degree of a graph. Discrete Math., 301(2005), 243-246.