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, deg_G(v), is defined as the size of {w ∈ V (G) | vw ∈ E(G)}. A vertex of degree one is called a pendant vertex.

The number of vertices of degree i in G is denoted by n_i = n_i(G). Obviously ∑_i≥1n_i = |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 d_G(u, v) between two vertices u and v of G is the length of a shortest u − v path in G, and the diameter is defined as diam(G) = max{d_G(u, v) | u, v ∈ V (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) = m− n + 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 G − E′ of G is obtained by deleting the edges of E′. If uv ∉ E(G), then the graph G + uv obtained from G by attaching vertices u, v.

Suppose r = (r₁, r₂, … , r_n) and s = (s₁, s₂, … , s_n) are two non-increasing vectors in ℝⁿ. If ∑i=1kri≤∑i=1ksi, 1 ≤ k ≤ n−1, and ∑i=1nri≤∑i=1nsi, then we say that r is majorized by s, and we write r ⪯ s. Moreover, r ≺ s means that r ⪯ s and r ≠ s, see [10] for details. The non-increasing sequence d = (d₁, d₂, … , d_n) of nonnegative integers is called a graphic sequence if we can find a simple graph G with the vertex set V (G) = {v₁, v₂, … , v_n} such that d_i = deg_G(v_i), 1 ≤ i ≤ n. 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, GA₁-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.

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 γ, thenn1(G)=2-2γ+∑i=3Δ(G)(i-2)niandn2(G)=2γ+n-2-∑i=3Δ(G)(i-1)ni.

Proposition 2.2

Let G be a connected graph with m edges.

• (1) If G ≅ P_n, then γ(G) = m − diam(G) − n₁ + 2.

• (2) If G ≇ P_n, then γ(G) ≤ m − diam(G) − n₁ + 1.

Corollary 2.3

Let G be a connected graph with n vertices and m edges except P_n. Then diam(G) ≤ n − n₁ + 1. Furthermore, if G is a chemical graph, thendiam(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 G ≅ P_n, then diam(G) = 2R(G) − n₁ − 1.

• (2) If G ≇ P_n, then diam(G) ≤ 4R(G) − n₁.

Corollary 2.5

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

Corollary 2.6

Let G be a connected chemical graph with n vertices and m edges. ThenR(G)≥32n-m, with equality if and only if G ≇ P_nor C_n.

Corollary 2.7

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

• (1) If G is a tree, thenR(G)≥12n+1, with equality if and only if G ≇ P_n.

• (2) If G is unicyclic, thenR(G)≥12n, with equality if and only if G ≇ C_n.

For n ≥ 5 we set

Corollary 2.8

Let G be a chemical bicyclic graph with n ≥ 5 vertices. If B₁ ∈ Γ₁, B₂ ∈ Γ₂and G ∉ Γ₁ ∪ Γ₂, thenR(B1)<R(B2)=12n-14<R(G).

Corollary 2.9

Let G be a chemical tricyclic graph with n ≥ 5 vertices. If G₁ ∈ Λ₁, G₂ ∈ Λ₂and G ∉ Λ₁ ∪ Λ₂, thenR(G1)<R(G2)=12n+512<R(G).

Corollary 2.10

Let G be a chemical tetracyclic graph with n ≥ 6 vertices. If G₁ ∈ Θ₁and G₂ ∈ Θ₂and G ∉ Θ₁ ∪ Θ₂, thenR(G1)<R(G2)=12n+1312<R(G).

For n ≥ 8 we define

Corollary 2.11

Let G be a chemical pentacyclic graph with n ≥ 6 vertices. If G₁ ∈ ϒ₁, G₂ ∈ ϒ₂and G ∉ ϒ₁ ∪ ϒ₂, thenR(G1)<R(G2)=12n+74<R(G).

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 Λ ⊂ ℝⁿ is said to be Schurconvex on Λ if for all x = (x₁, … , x_n) and y = (y₁ … , y_n) ∈ Λ, if x ⪯ y, then ϕ(x) ≤ ϕ(y). In addition, ϕ is said to be strictly Schur-convex on Λ if x ≺ y 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 Iⁿ.

Theorem 3.2

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

Lemma 3.3

(See [7]) Suppose that G₁is a graph with given vertices v₁and v₂, such that deg_G1 (v₁) ≥ 2 and deg_G1 (v₂) = 1. In addition, assume that G₂is another graph and w is a vertex in G₂. Let G be the graph obtained from G₁and G₂by attaching vertices w and v₁. If G′ = G − wv₁ + wv₂, then d(G′) ≺ d(G).

Theorem 3.4

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

has the maximal inverse degree and a graphGγ2with the degree sequence

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

Theorem 3.5

Let T_i ∈ A_i, for 1 ≤ i ≤ 31 (SeeTable 1). If n ≥ 22 and T is a tree such thatT∉∪i=131Ai, then R(T_i) < R(T_i+1) for i ∈ {1, 2, … , 29}\ {25}, R(T₂₅) = R(T₂₆), R(T₃₀) = R(T₃₁) and R(T₃₁) < R(T).

Theorem 3.6

Let U_i ∈ B_i, for 1 ≤ i ≤ 41 and U₄₂ ∈ B₄₃(See Table 2). If n ≥ 24 and U is a chemical unicyclic graph such thatU∉∪i=141Bi∪B43, then for i ∈ {1, 2, … , 40}\ {25, 30, 36}, R(U_i) < R(U_i+1)

and R(U₄₂) < R(U).

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