Kyungpook Mathematical Journal 2020; 60(3): 467-475
Published online September 30, 2020
Copyright © Kyungpook Mathematical Journal.
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 : firstname.lastname@example.org
Department of Pure Mathematics, Faculty of Mathematical Science, University of Kashan, Kashan 87317-53153, Iran
e-mail : email@example.com and firstname.lastname@example.org
Received: June 20, 2019; Revised: April 21, 2020; Accepted: April 22, 2020
Keywords: diameter, cyclomatic number, pendant vertex, inverse degree, chemical graph
Throughout this paper, all graphs are assumed to be undirected, simple and connected. Let
The number of vertices of degree
The cyclomatic number of a connected graph
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
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:
If G≅ P n, then γ( G) = m− diam( G) − n1 + 2.
If G≇ P n, then γ( G) ≤ m− diam( G) − n1 + 1.
It is clear that
By Proposition 2.2, we have diam(
If G≅ P n, thendiam( G) = 2 R( G) − n1 − 1.
If G≇ P n, thendiam( G) ≤ 4 R( G) − n1.
It is easy to see that diam(
By Proposition 2.2, and the fact that
Now, by Lemma 2.1. and
If G is a tree, then , with equality if and only if G≇ P n.
If G is unicyclic, then , with equality if and only if G≇ C n.
By Corollary 2.5, if
By Corollary 2.5, if
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
3. Ordering Chemical Trees and Unicyclic Graphs with Respect to the Inverse Degree Index
Recall that if
By data given in the Table 1, and simple calculations one can see that,
By Table 2, we can see that, for
The research of the second and the third authors was partially supported by the University of Kashan under grant no 364988/180.
- X. Chen, and S. Fujita.
On diameter and inverse degree of chemical graphs. Appl Anal Discrete Math., 7(2013), 83-93.
- KC. Das, K. Xu, and J. Wang.
On inverse degree and topological indices of graphs. Filomat., 30(8)(2016), 2111-2120.
- D. Dimitrov, and A. Ali.
On the extremal graphs with respect to variable sum exdeg index. Discrete Math Lett., 1(2019), 42-48.
- 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.
- P. Erdös, J. Pach, and J. Spencer.
On the mean distance between points of a graph. Congr Numer., 64(1988), 121-124.
- S. Fajtlowicz.
On conjectures of graffiti II. Congr Numer., 60(1987), 189-197.
- A. Ghalavand, and AR. Ashrafi.
Extremal graphs with respect to variable sum exdeg index via majorization. Appl Math Comput., 303(2017), 19-23.
- 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.
- 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.
- 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.
- K. Xu, . Kexiang, and K. Ch Das.
Some extremal graphs with respect to inverse degree. Discrete Appl Math., 203(2016), 171-183.
- Z. Zhang, J. Zhang, and X. Lu.
The relation of matching with inverse degree of a graph. Discrete Math., 301(2005), 243-246.