# On the Inverse Problem for Some Topological Indices

Authors: Durbar Maji; Ganesh Ghorai; Muhammad Khalid Mahmood; Md. Ashraful Alam
Journal: Journal of Mathematics
 (2021)

---

## Abstract

The study of the inverse problem (IP) based on the topological indices (TIs) deals with the numerical relations to TIs. Mathematically, the IP can be expressed as follows: given a graph parameter/TI that assigns a non-negative integer valueg to every graph within a given family G of graphs, find some G∈G for which TIG=g. It was initiated by the Zefirov group in Moscow and later Gutman et al. proposed it. In this paper, we have established the IP only for the Y-index, Gourava indices, second hyper-Zagreb index, reformulated first Zagreb index, and reformulated F-index since they are closely related to each other. We have also studied the same which is true for the molecular, tree, unicyclic, and bicyclic graphs.


---

## Body

## 1. Introduction

Throughout the paper, we considerŁ=VŁ,EŁ as a simple (without loops and multiple edge loops) finite graph that contains VŁ=n vertices and EŁ=m edges, respectively. The notation du/Ł denotes the degree of a vertex u∈VŁ. All other notations and terminologies used but not clearly stated in this paper may be followed from [1].In chemical graph theory, a TI, usually known as a molecular descriptor, can be expressed by a real number calculated from a chemical/molecular graph which is the representation of a chemical compound by replacing atoms with vertices and bonds with edges. The TI is calculated for evaluating the information about the atomic constitution and bond characteristics of a molecule/chemical compound. The TI of a molecular graph is a numerical number that enables us to collect information about the concerned chemical structure. It helps us to know its hidden properties without performing experiments [2–4]. The TIs also correlate and predict several physical, chemical, biological, pharmaceutical, pharmacological activities/properties from molecular structures of graphs corresponding to real-life situations. The IP is defined as the feasibility of finding/modeling the chemical structure represented by a graph whose index value is equal to a given non-negative integer for the integer-valued problem. In the QSAR and QSPR studies [5], a method by which it is possible to predict the properties of a given molecular structure is called a forward problem. The inverse problem is concerned that, one can design the exact molecular structure that satisfies the given target properties by applying the forward problem solution.The most popular as well as the oldest degree-based graph indices are the first and second Zagreb indices. Gutman et al. introduced the first Zagreb indexM1Ł in [6] and second Zagreb index M2Ł in [7]. They are defined, respectively, as(1)M1Ł=∑u∈VŁd2uŁ=∑uv∈EŁduŁ+dvŁ,M2Ł=∑uv∈EŁduŁdvŁ.In 2016, Farahani et al. [8] defined the second hyper-Zagreb index as follows:(2)HM2Ł=∑uv∈EŁduŁdvŁ2.Kulli [9] introduced the first and second Gourava indices, defined, respectively, as(3)GO1Ł=∑uv∈EŁduŁ+dvŁ+duŁdvŁ,GO2Ł=∑uv∈EŁduŁ+dvŁduŁdvŁ.Milicevic proposed the reformulated first Zagreb indexEM1Ł in [10], defined as(4)EM1Ł=∑e∈EŁd2eŁ;deŁ=duŁ+dvŁ−2.Liu et al. [11] put forward the reformulated F-index, and it is defined as follows:(5)RFŁ=∑e∈EŁd3eŁ=∑e∼f∈EŁd2eŁ+d2fŁ.Alameri et al. [12] introduced Y-index, and it is defined by(6)YŁ=∑u∈VGd4uŁ=∑uv∈EŁd3uŁ+d3vŁ.Graph theory, a branch of mathematics, provides the tools for solving problems of information theory, computer sciences, physics, and chemistry [13–15]. The study of the IP is encountered in various fields of science, especially in mathematics and chemistry. The IP for a TI is defined as follows: for a given TI and a non-negative integer value x, find (chemical) graph Ł for which TIŁ=x. Also, the inverse existence problem [16] for the pair G,Γ can be asked as follows: given G a class of graph and function Γ:G⟶H, for which g∈H there is G∈G with ΓG=g? The idea of the IP based on TIs was initiated by the Zefirov group in Moscow [5, 17, 18] and was first proposed by Gutman et al. in [19]. The IP for Wiener index was solved in [20]. In [21], the IP was studied for sigma index as well as for acyclic, unicyclic, and bicyclic graphs. The same problem for the Steiner Wiener index was also solved in [22]. This type of problem for the Zagreb indices, forgotten Zagreb index, and the hyper-Zagreb index was studied in [23]. Tavakoli et al. [24] addressed the IP for first Zagreb index. Also, the IP for some graph indices was investigated in [25]. In [26], Czabarka et al. solved the IP for certain tree parameters. To study more about the inverse problems and the topological indices of graph operations, one can see these references [27–32].There are so many benefits in the solution of IP. It helps to design of combinatorial libraries for drug discovery in combinatorial chemistry [33]. It may be helpful in speeding up the discovery of lead compounds with desired properties [34]. Also, the IP plays its significance in the application of trees [35] such as the field of algorithms, chemical graph theory, signal processing, and electrical circuits.


## 2. Preliminaries

To study the IP forY-index, we will use the following crucial observation.Let Ł be a graph havingu and v as vertices which are adjacent to each other. We subdivide each edge uv by introducing a new vertex w (of degree 2) to construct a new graph Ł∗ (see Figure 1).Figure 1
The graphs (a) Ł and (b) Ł∗ used in auxiliary Lemmas 1–4.Here, theY-index of the new graph Ł∗ will be sixteen which is more than the graph Ł.Lemma 1.
By applying the transformationŁ⟶Ł∗, the Y-index value will be increased by 16. That is, YŁ∗=YŁ+16.Proof.
Let us consider the graph Ł with verticesu and v of degrees x and y, respectively. Since in the new constructed graph Ł∗, a new vertex w is inserted between u and v,(7)YŁ∗−YŁ=d4uŁ∗+d4wŁ∗+d4vŁ∗−d4uŁ−d4vŁ=x4+16+y4−x4−y4=16.Lemma 2.
If eitherdu/Ł=2 or dv/Ł=2 (or both), then by the means of the above transformation Ł⟶Ł∗, the value of the first Gourava index increases by 8. That is,(8)GO1Ł∗=GO1Ł+8.
Similarly, the value of the second Gourava index increases by 16. Thus,(9)GO2Ł∗=GO2Ł+16.Lemma 3.
If eitherdu/Ł=2 or dv/Ł=2 (or both), then by means of the above transformation Ł⟶Ł∗, the value of the second hyper-Zagreb index increases by 16. That is,(10)HM2Ł∗=HM2Ł+16.Lemma 4.
If eitherdu/Ł=2 or dv/Ł=2 (or both), then by applying the transformation Ł⟶Ł∗, the values of the reformulated first Zagreb index and reformulated F-index of the graph Ł increase by 4 and 8, respectively. Thus,(11)EM1Ł∗=EM1Ł+4,RFŁ∗=RFŁ+8.


## 3. Main Results and Discussion

In graph theory, the IP based on the TIs is an interesting one among the problems associated with the estimation of different graph invariants/TIs such as chromatic number, connectivity, girth, and number of independent sets. The IP plays a crucial role in many areas of science, especially in mathematics. In this section, we have investigated the IP forY-index, Gourava indices, second hyper-Zagreb index, reformulated first Zagreb index, and reformulated F-index. Additionally, we have developed the same problem for molecular, tree, acyclic, unicyclic, and bicyclic graphs.


### 3.1. The IP forY-Index

Here we will discuss the IP forY-index.Theorem 1.
TheY-index for connected graphs can take all positive even integers, except for 4,6,8,10,12,14,16,28i+2,28j+3,28k+4,28m+5,28n+6,28p+7 where i=1,2,…,4;j=1,2,…,9;k=1,2,…,14;m=1,2,…,19;n=1,2,…,24; and p=1,2,…,29.Proof.
Proof. To prove the theorem, we establish a set of graphsY0,Y2,Y4,Y6,Y8,Y10,Y12,Y14 whose Y-index values are 48, 2, 84, 166, 248, 330, 412, and 494, respectively. These numbers are congruent to 0, 2, 4, 6, 8, 10, 12, and 14 (mod 16), respectively.
Consider the cyclic graphsCn for n≥3. Clearly, in Figure 2(a), YY0=C3=48, YC4=64, YC5=80, and YCn=16n for n≥3. Now we apply Lemma 1 for each graph in Figure 2. Thus, YY0 takes all those even positive integer values which are divisible by 16, except 16 and 32.
In Figure2(b), YP2=2. By applying the transformation in Lemma 1, we arrive at graphs whose Y-index values are 18,34,50,66, and so on. There are the path graphs. Thus, YŁ takes all positive even integer values which are congruent to 2 (mod 16).
Now consider the graph in Figure2(c) with YY4=84. By applying Lemma 1, we can obtain graphs with Y-index values 100,116,132,148,…. Here, YY4 contains all positive even integer values ≡ 4 (mod 16), except the integers 20,36,52,and68.
The graph is depicted in Figure2(d) with YY6=166, and then by using Lemma 1, we can take the graphs with Y-index values 182,198,214,230,…, and so on. Therefore, YY6 covers all positive even integer values ≡ 6 (mod 16) and ≥166. Obviously, the integers 6,22,…,134,150 are not covered by the construction.
In Figure2(e), we have YY8=248, and then by using Lemma 1, we can take the graphs with Y-index values 264,280,296,314,…, and so on. So, YY8 takes all positive even integer values ≡ 8 (mod 16) and ≥248. Obviously, the integers 24,40,…,216,232 are not covered by the construction.
The graph in Figure2(f) contains YY10=330. Again by Lemma 1, YY10 goes to all those positive even integer values ≡ 10 (mod 16) and ≥330 giving 330, 348, 364, 380, …, and so on.
From Figure2(g), we have YY12=412. By applying Lemma 1, YY12 takes all positive even integer values ≡ 12 (mod 16) and also ≥412 having 412, 428, 444, 460, …, and so on.
The graph in Figure2(h) has YY14=494. By applying Lemma 1, YY14 takes all positive even integer values ≡ 14 (mod 16) and also ≥494 taking 494, 510, 526, 542, …, and so on. There exist no connected graphs with the Y-indices mentioned in Table 1.Figure 2
The graphsYi, for i = 0, 2, 4, 6, 8, 10, 12, and 14: (a) Y0, (b) Y2, (c) Y4, (d) Y6, (e) Y6, (f) Y8, (g) Y10, (h) Y12, and (i) Y14.Table 1
Y-index values which do not exist.
Y0Y4Y6Y8Y10Y12Y14468, 2410, 2612, 28, 4414, 30, 4616202240, 5642, 5860, 76, 9262, 78, 9432363872, 8874, 90108, 124, 140110, 126, 1425254104, 120106, 122156, 172, 188158, 174, 1906870136, 152138, 154204, 220, 236206, 222, 23886168, 184170, 186252, 268, 284254, 270, 286102200, 216202, 218300, 316, 332302, 318, 334118232234, 250348, 364, 380350, 366, 382134266, 282396398, 414, 430150298, 314446, 462, 478Corollary 1.
TheY-index of a tree (or molecular) graph can take all positive even integers, except for 4,6,8,10,12,14,16,28r+2,28s+3,28t+4,28w+5,28x+6,28y+7 where r=1,2,3,4;s=1,2,…,9;t=1,2,…,14;w=1,2,…,19;x=1,2,…,24; and y=1,2,…,29.Corollary 2.
Let Ł be a connected unicyclic or bicyclic graph. Then, there exists theY-index of the form 16h+2k for all non-negative integers where h≠0 and 1≤k≤7.Proof.
Proof. LetŁ1 be a unicyclic graph which is obtained by adding a path of length two to any vertex u of the cyclic graph Cn for n=5. Thus, YŁ1=162=16×10+2×1. Similarly, the unicyclic graph Ł2 is obtained by adding another path of length two to one of the two adjacent vertices to u that lie on Ł1 (see Figure 3). We get YŁ2=244.
The bicyclic graphŁ3 is obtained by gluing two cyclic graphs with one side of both, and we have YŁ3=306 which also can be expressed in the said form. Similarly, another bicyclic graph Ł4 is obtained by adding a path with length two to any vertex u of Ł3. Thus, YŁ4=388 is of the form 16h+2k for h=24,k=2.Figure 3
The graphsŁ1,Ł2,Ł3, and Ł4 with Y-index values: (a) let Ł1 be a unicyclic graph with YŁ1=162, (b) let Ł2 be a unicycle graph with YŁ3=244, (c) let Ł3 be a bicyclic graph with YŁ3=306, and (d) let Ł4 be a bicyclic graph with YŁ4=388.
(a)(b)(c)(d)


### 3.2. The IP for Gourava Indices

Here we study the IP for Gourava indices.Theorem 2.
The first Gourava index of a connected graph can take any positive integer except for 1, 2, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 19, 20, 22, 23, 25, 27, 28, 29, 31, 33, 35, 41, 44, 49, 57, and 73.Proof.
By applying Lemma2, we construct eight series of graphs Gj,j=0,1,2,…,7 containing at least one vertex of degree 2, whose GO1-values are of the form 8s+t for t=0,1,2,…,7. These graphs are drawn in Figures 4(a)–4(h).
Consider a cycle graphCn with n≥3. Clearly, GO1Cn=8n. Therefore, GO1Ł can take all those positive integer values which are divisible by 8. From the graph G0 (Figure 4) and Lemma 2, we obtain the graphs with GO1Ł-values 32,40,48,56,64,…. Thus, GO1Ł takes all positive integers ≡0 (mod 8) and ≥24.
Consider the graphG1 in Figure 4 with GO1Ł=81, i.e., GO1Ł implies all positive integer values ≡1 (mod 8). Then, by Lemma 2, we obtain graphs with GO1Ł = 89, 97, 105, 113, 121, …. Again for the graph G2, GO1Ł=10. Thus, we can arrive at graphs whose GO1 values are 18, 26, 34, 42, 50, 58, 66, 74, 82, …. Similarly, by applying Lemma 2 to the graphs G3, G4, G5, G6, and G7, we get the graphs with GO1 = 59, 67, 75, 83, 91, 99, 107, 115, …, 60, 68, 76, 84, 92, 100, 108, …, 45, 53, 61, 69, 77, 85, …, 38, 46, 54, 62, 70, 78, …, and 47, 55, 63, 71, 79, 87, …, respectively. The star graphs S4, S5 and examples depicted in Figures 2(d) and 5(b) show that there exist graphs with GO1Ł as 21, 36, 43, and 65, respectively. There exist no connected graphs with first Gourava index as listed in Table 2.Figure 4
The graphsGj, for j=0,1,2,…,7 with first Gourava index values: (a) G0GO1G0=24, (b) G1GO1G1=81, (c) G2GO1G2=10, (d) G3GO1G3=51, (e) G4GO1G4=52, (f) G5GO1G5=37, (g) G6GO1G6=30, and (h) G7GO1G7=39.
(a)(b)(c)(d)(e)(f)(g)(h)Figure 5
The star graph (a)S6 and tree (b) T with second hyper-Zagreb index values.
(a)(b)Table 2
The first Gourava index values which do not exist.
G0G1G2G3G4G5G6G71245678911121314151617, 251920222333, 412728293149, 57357344Corollary 3.
The first Gourava index of a tree (or molecular) graph can take any positive integer, except for 1, 2, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 19, 20, 22, 23, 25, 27, 28, 29, 31, 33, 35, 41, 44, 49, 57, and 73.Now we study to settle the IP for the second Gourava index.Theorem 3.
The second Gourava index of a connected graph can take any positive even integer except for 4, 6, 8, 10, 14, 16, 20, 22, 24, 26, 30, 32, 34, 38, 40, 42, 46, 50, 52, 54, 56, 58, 62, 66, 68, 70, 72, 74, 78, 82, 86, 90, 94, 98, 102, 106, 110, 118, 122, and 134.Proof.
Consider first path graphsPn for n≥2. It is clear that GO2P2=2 and GO2P3=12. By Lemma 2, since GO2Pn=16n−36 for n≥3, we obtain the graphs whose GO2-values are 28, 44, 60, 76, 92, 108, … which are congruent to 12 (mod 16). If we consider a cyclic graph Cn with n vertices, then GO2Cn=16n for n≥3. Clearly, we get the graphs with GO2-values 48, 64, 80, 96, 112, …. Now the graph G7 drawn in Figure 4 has GO2Ł=84. Therefore, by applying Lemma 2, we obtain the graphs with second Gourava index values 100, 116, 132, 148, 164, …. The graphs G4 and G5 in Figure 4 contain GO2Ł=126 and GO2Ł=88, respectively. Therefore, by Lemma 2, GO2Ł obtains all those even integer values 126, 142, 158, 174, 190, 206, 222, … and 104, 120, 136, 152, …, respectively. In same procedure, from Figure 4, we get the graph G3 with GO2Ł=138. So, it follows the GO2-values 154, 170, 186, 202, 218, ….
In Figure6, by Lemma 2, we have GO2 (G8) = 150 and GO2 (G9) = 114 with. Then by using the Lemma 2, we can take the graphs with 166, 182, 198, 214, … and 130, 146, 162, 178, 194, …, respectively. The integers not covered by the above transformation for the second Gourava index are listed in Table 3.Figure 6
The graphs (a)G8 and (b) G9 with second Gourava index values.Table 3
The second Gourava index values which do not exist.
G0G2G4G6G8G10G1446810141620222426303234384042465052545658626668707274788286909498102106110118122134Corollary 4.
The second Gourava index of a tree (or molecular) graph can take any positive even integer, except for 4, 6, 8, 10, 14, 16, 20, 22, 24, 26, 30, 32, 34, 38, 40, 42, 46, 50, 52, 54, 56, 58, 62, 66, 68, 70, 72, 74, 78, 82, 86, 90, 94, 98, 102, 106, 110, 118, 122, and 134.


### 3.3. The IP for Second Hyper-Zagreb Index

Theorem 4.
The second hyper-Zagreb index of a connected graph can be any positive integer, except 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 26, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 41, 42, 43, 44, 45, 46, 47, 49, 50, 51, 52, 53, 54, 55, 57, 59, 60, 61, 62, 63, 65, 66, 67, 68, 69, 70, 71, 73, 75, 76, 77, 78, 79, 81, 82, 83, 84, 85, 86, 87, 91, 92, 93, 94, 95, 98, 99, 100, 101, 102, 103, 107, 109, 110, 111, 114, 115, 118, 119, 123, 126, 127, 130, 131, 133, 134, 135, 141, 142, 143, 146, 147, 149, 150, 151, 157, 158, 159, 163, 165, 167, 173, 174, 175, 181, 183, 190, 191, 199, 206, 215, 222, 223, 231, 239, 255, and 271.Proof.
We construct a series of sixteen graphs such asH0,H1,H2,…,H15. The HM2 values of these graphs can be expressed in the form 16h+i for i=0,1,2,…,15. In Figure 7, we construct the graphs Hk for k=2,3,4,5,6,7 and 11,12,13,14,15. Note that the graphs H0,H1,H8,H9,H10 are similar to Figures 4(a), 4(f), 4(c), 4(h), and 4(g) respectively. We have HM2 (H0) = 48. Then by using Lemma 3, we can take the graphs with HM2 values 64, 80, 96, 112, … which are congruent to 0 (mod 16). Secondly, consider the graph H1 which generates the HM2-values 97,113,129,145,161,…, and all these are congruent to 1 (mod 16).
SinceHM2(H2) = 162, by mean of the construction method upon the graph H2 from the Lemma 3, we get the graphs with HM2 values 178, 194, 210,226, … which are congruent to 2 (mod 16). For H3, the HM2-values cover the integers 179,195,211,227,… which are ≡3 (mod 16). Analogously, the HM2 values for the graph H4 cover all the integers 116,132,148,…., and all these numbers are congruent to 4 (mod 16). For H5, it provides the HM2 values 197,213,229,… which are ≡5 (mod 16). For H6 there exist HM2 values 166,182,198,… which are ≡6 (mod 16). It follows 247,263,379,… for the graph H7, and these integers are congruent to 7 (mod 16). Similarly by Lemma 3, we get for the graphs H8,H9,H10,H11,H12,H13,H14,H15 with Now, using the construction method in Lemma 3 to H8,H9,H10,H11,H12,H13,H14, and H15, we can generate the graphs with HM2 values 8, 24, 40, … congruent to 8 (mod 16); 89, 105, 121, … congruent to 9 (mod 16); 58, 74, 90, … congruent to 10 (mod 16); 139, 155, 171, … congruent to 11 (mod 16); 108, 124, 140, … congruent to 12 (mod 16); 189, 205, 221, … congruent to 13 (mod 16); 238, 254, 270, … congruent to 14 (mod 16); and 257, 303, 319, … congruent to 15 (mod 16), respectively.
The examples drawn in the Figures2(c), 2(d), 5(a), and 5(b) have HM2 values 117,27,125, and 207, respectively. These numbers are congruent to 5,11,13, and 15 (mod 16), chronologically. There exist no connected graphs with the HM2-indices mentioned in Table 4.Figure 7
The graphsHk, for k = 2, 3, 4, 5, 6, 7 and 11, 12, 13, 14, 15.Table 4
HM2 values which do not exist.
H0H1H2H3H4H5H6H7H9H10H11H12H13H14H152345679101112131415161718192021222325262829303132333435363738394142434445464749505152535455575960616263656667686970717375767778798182838485868791929394959899100101102103107109110111114115118119123126127130131133134135141142143146147149150151157158159163165167173174175181183190191199206223, 239215, 231222255, 271Corollary 5.
The second hyper-Zagreb index of a tree (or molecular) graph can be any positive integer, except 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 26, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 41, 42, 43, 44, 45, 46, 47, 49, 50, 51, 52, 53, 54, 55, 57, 59, 60, 61, 62, 63, 65, 66, 67, 68, 69, 70, 71, 73, 75, 76, 77, 78, 79, 81, 82, 83, 84, 85, 86, 87, 91, 92, 93, 94, 95, 98, 99, 100, 101, 102, 103, 107, 109, 110, 111, 114, 115, 118, 119, 123, 126, 127, 130, 131, 133, 134, 135, 141, 142, 143, 146, 147, 149, 150, 151, 157, 158, 159, 163, 165, 167, 173, 174, 175, 181, 183, 190, 191, 199, 206, 215, 222, 223, 231, 239, 255, and 271.


### 3.4. The IP for Reformulated First Zagreb Index

Theorem 5.
The first reformulated Zagreb index of a connected graph can take all positive even integer values except for 4 and 8.Proof.
At first, we consider the pathPn with n≥3. The Rez-value for P3 is equal to 2. By Lemma 4, we obtain graphs with Rez-values 6, 10, 14, 18, …, and so on. Also, since RezS3=12, by means of the construction described in Lemma 4, we have the graphs whose Rez-values are 16, 20, 24, 28, 32, 36, 40, …. Hence, RezŁ covers all positive even integers except 4 and 8.Corollary 6.
The first reformulated Zagreb index of a tree (or molecular) graph can take all positive even integer values, except for 4 and 8.


### 3.5. The IP for ReformulatedF-Index

Theorem 6.
The reformulatedF-index of a connected graph can be any positive even integer, except for 4, 6, 8, 12, 14, 16, 20, 22, 28, 30, 36, 38, 46, 54, and 62.Proof.
For the path graphsP3, we get RFP3=2. Thus, by applying Lemma 4, we obtain graphs with RFŁ-values equal to 10, 18, 26, 34, …. Similarly, for the cyclic graph C3, we have RFC3=24 and next obtained graphs having RFŁ-values 32, 40, 48, 56, …. In an analogous manner, starting with G5 and G6 in Figure 4, we obtain the graphs with RF-values 78, 86, 94, 102, … and 52, 60, 68, 76, …, respectively.Corollary 7.
The reformulatedF-index of a tree (or molecular) graph can be any positive even integer, except for 4, 6, 8, 12, 14, 16, 20, 22, 28, 30, 36, 38, 46, 54, and 62.


## 3.1. The IP forY-Index

Here we will discuss the IP forY-index.Theorem 1.
TheY-index for connected graphs can take all positive even integers, except for 4,6,8,10,12,14,16,28i+2,28j+3,28k+4,28m+5,28n+6,28p+7 where i=1,2,…,4;j=1,2,…,9;k=1,2,…,14;m=1,2,…,19;n=1,2,…,24; and p=1,2,…,29.Proof.
Proof. To prove the theorem, we establish a set of graphsY0,Y2,Y4,Y6,Y8,Y10,Y12,Y14 whose Y-index values are 48, 2, 84, 166, 248, 330, 412, and 494, respectively. These numbers are congruent to 0, 2, 4, 6, 8, 10, 12, and 14 (mod 16), respectively.
Consider the cyclic graphsCn for n≥3. Clearly, in Figure 2(a), YY0=C3=48, YC4=64, YC5=80, and YCn=16n for n≥3. Now we apply Lemma 1 for each graph in Figure 2. Thus, YY0 takes all those even positive integer values which are divisible by 16, except 16 and 32.
In Figure2(b), YP2=2. By applying the transformation in Lemma 1, we arrive at graphs whose Y-index values are 18,34,50,66, and so on. There are the path graphs. Thus, YŁ takes all positive even integer values which are congruent to 2 (mod 16).
Now consider the graph in Figure2(c) with YY4=84. By applying Lemma 1, we can obtain graphs with Y-index values 100,116,132,148,…. Here, YY4 contains all positive even integer values ≡ 4 (mod 16), except the integers 20,36,52,and68.
The graph is depicted in Figure2(d) with YY6=166, and then by using Lemma 1, we can take the graphs with Y-index values 182,198,214,230,…, and so on. Therefore, YY6 covers all positive even integer values ≡ 6 (mod 16) and ≥166. Obviously, the integers 6,22,…,134,150 are not covered by the construction.
In Figure2(e), we have YY8=248, and then by using Lemma 1, we can take the graphs with Y-index values 264,280,296,314,…, and so on. So, YY8 takes all positive even integer values ≡ 8 (mod 16) and ≥248. Obviously, the integers 24,40,…,216,232 are not covered by the construction.
The graph in Figure2(f) contains YY10=330. Again by Lemma 1, YY10 goes to all those positive even integer values ≡ 10 (mod 16) and ≥330 giving 330, 348, 364, 380, …, and so on.
From Figure2(g), we have YY12=412. By applying Lemma 1, YY12 takes all positive even integer values ≡ 12 (mod 16) and also ≥412 having 412, 428, 444, 460, …, and so on.
The graph in Figure2(h) has YY14=494. By applying Lemma 1, YY14 takes all positive even integer values ≡ 14 (mod 16) and also ≥494 taking 494, 510, 526, 542, …, and so on. There exist no connected graphs with the Y-indices mentioned in Table 1.Figure 2
The graphsYi, for i = 0, 2, 4, 6, 8, 10, 12, and 14: (a) Y0, (b) Y2, (c) Y4, (d) Y6, (e) Y6, (f) Y8, (g) Y10, (h) Y12, and (i) Y14.Table 1
Y-index values which do not exist.
Y0Y4Y6Y8Y10Y12Y14468, 2410, 2612, 28, 4414, 30, 4616202240, 5642, 5860, 76, 9262, 78, 9432363872, 8874, 90108, 124, 140110, 126, 1425254104, 120106, 122156, 172, 188158, 174, 1906870136, 152138, 154204, 220, 236206, 222, 23886168, 184170, 186252, 268, 284254, 270, 286102200, 216202, 218300, 316, 332302, 318, 334118232234, 250348, 364, 380350, 366, 382134266, 282396398, 414, 430150298, 314446, 462, 478Corollary 1.
TheY-index of a tree (or molecular) graph can take all positive even integers, except for 4,6,8,10,12,14,16,28r+2,28s+3,28t+4,28w+5,28x+6,28y+7 where r=1,2,3,4;s=1,2,…,9;t=1,2,…,14;w=1,2,…,19;x=1,2,…,24; and y=1,2,…,29.Corollary 2.
Let Ł be a connected unicyclic or bicyclic graph. Then, there exists theY-index of the form 16h+2k for all non-negative integers where h≠0 and 1≤k≤7.Proof.
Proof. LetŁ1 be a unicyclic graph which is obtained by adding a path of length two to any vertex u of the cyclic graph Cn for n=5. Thus, YŁ1=162=16×10+2×1. Similarly, the unicyclic graph Ł2 is obtained by adding another path of length two to one of the two adjacent vertices to u that lie on Ł1 (see Figure 3). We get YŁ2=244.
The bicyclic graphŁ3 is obtained by gluing two cyclic graphs with one side of both, and we have YŁ3=306 which also can be expressed in the said form. Similarly, another bicyclic graph Ł4 is obtained by adding a path with length two to any vertex u of Ł3. Thus, YŁ4=388 is of the form 16h+2k for h=24,k=2.Figure 3
The graphsŁ1,Ł2,Ł3, and Ł4 with Y-index values: (a) let Ł1 be a unicyclic graph with YŁ1=162, (b) let Ł2 be a unicycle graph with YŁ3=244, (c) let Ł3 be a bicyclic graph with YŁ3=306, and (d) let Ł4 be a bicyclic graph with YŁ4=388.
(a)(b)(c)(d)


## 3.2. The IP for Gourava Indices

Here we study the IP for Gourava indices.Theorem 2.
The first Gourava index of a connected graph can take any positive integer except for 1, 2, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 19, 20, 22, 23, 25, 27, 28, 29, 31, 33, 35, 41, 44, 49, 57, and 73.Proof.
By applying Lemma2, we construct eight series of graphs Gj,j=0,1,2,…,7 containing at least one vertex of degree 2, whose GO1-values are of the form 8s+t for t=0,1,2,…,7. These graphs are drawn in Figures 4(a)–4(h).
Consider a cycle graphCn with n≥3. Clearly, GO1Cn=8n. Therefore, GO1Ł can take all those positive integer values which are divisible by 8. From the graph G0 (Figure 4) and Lemma 2, we obtain the graphs with GO1Ł-values 32,40,48,56,64,…. Thus, GO1Ł takes all positive integers ≡0 (mod 8) and ≥24.
Consider the graphG1 in Figure 4 with GO1Ł=81, i.e., GO1Ł implies all positive integer values ≡1 (mod 8). Then, by Lemma 2, we obtain graphs with GO1Ł = 89, 97, 105, 113, 121, …. Again for the graph G2, GO1Ł=10. Thus, we can arrive at graphs whose GO1 values are 18, 26, 34, 42, 50, 58, 66, 74, 82, …. Similarly, by applying Lemma 2 to the graphs G3, G4, G5, G6, and G7, we get the graphs with GO1 = 59, 67, 75, 83, 91, 99, 107, 115, …, 60, 68, 76, 84, 92, 100, 108, …, 45, 53, 61, 69, 77, 85, …, 38, 46, 54, 62, 70, 78, …, and 47, 55, 63, 71, 79, 87, …, respectively. The star graphs S4, S5 and examples depicted in Figures 2(d) and 5(b) show that there exist graphs with GO1Ł as 21, 36, 43, and 65, respectively. There exist no connected graphs with first Gourava index as listed in Table 2.Figure 4
The graphsGj, for j=0,1,2,…,7 with first Gourava index values: (a) G0GO1G0=24, (b) G1GO1G1=81, (c) G2GO1G2=10, (d) G3GO1G3=51, (e) G4GO1G4=52, (f) G5GO1G5=37, (g) G6GO1G6=30, and (h) G7GO1G7=39.
(a)(b)(c)(d)(e)(f)(g)(h)Figure 5
The star graph (a)S6 and tree (b) T with second hyper-Zagreb index values.
(a)(b)Table 2
The first Gourava index values which do not exist.
G0G1G2G3G4G5G6G71245678911121314151617, 251920222333, 412728293149, 57357344Corollary 3.
The first Gourava index of a tree (or molecular) graph can take any positive integer, except for 1, 2, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 19, 20, 22, 23, 25, 27, 28, 29, 31, 33, 35, 41, 44, 49, 57, and 73.Now we study to settle the IP for the second Gourava index.Theorem 3.
The second Gourava index of a connected graph can take any positive even integer except for 4, 6, 8, 10, 14, 16, 20, 22, 24, 26, 30, 32, 34, 38, 40, 42, 46, 50, 52, 54, 56, 58, 62, 66, 68, 70, 72, 74, 78, 82, 86, 90, 94, 98, 102, 106, 110, 118, 122, and 134.Proof.
Consider first path graphsPn for n≥2. It is clear that GO2P2=2 and GO2P3=12. By Lemma 2, since GO2Pn=16n−36 for n≥3, we obtain the graphs whose GO2-values are 28, 44, 60, 76, 92, 108, … which are congruent to 12 (mod 16). If we consider a cyclic graph Cn with n vertices, then GO2Cn=16n for n≥3. Clearly, we get the graphs with GO2-values 48, 64, 80, 96, 112, …. Now the graph G7 drawn in Figure 4 has GO2Ł=84. Therefore, by applying Lemma 2, we obtain the graphs with second Gourava index values 100, 116, 132, 148, 164, …. The graphs G4 and G5 in Figure 4 contain GO2Ł=126 and GO2Ł=88, respectively. Therefore, by Lemma 2, GO2Ł obtains all those even integer values 126, 142, 158, 174, 190, 206, 222, … and 104, 120, 136, 152, …, respectively. In same procedure, from Figure 4, we get the graph G3 with GO2Ł=138. So, it follows the GO2-values 154, 170, 186, 202, 218, ….
In Figure6, by Lemma 2, we have GO2 (G8) = 150 and GO2 (G9) = 114 with. Then by using the Lemma 2, we can take the graphs with 166, 182, 198, 214, … and 130, 146, 162, 178, 194, …, respectively. The integers not covered by the above transformation for the second Gourava index are listed in Table 3.Figure 6
The graphs (a)G8 and (b) G9 with second Gourava index values.Table 3
The second Gourava index values which do not exist.
G0G2G4G6G8G10G1446810141620222426303234384042465052545658626668707274788286909498102106110118122134Corollary 4.
The second Gourava index of a tree (or molecular) graph can take any positive even integer, except for 4, 6, 8, 10, 14, 16, 20, 22, 24, 26, 30, 32, 34, 38, 40, 42, 46, 50, 52, 54, 56, 58, 62, 66, 68, 70, 72, 74, 78, 82, 86, 90, 94, 98, 102, 106, 110, 118, 122, and 134.


## 3.3. The IP for Second Hyper-Zagreb Index

Theorem 4.
The second hyper-Zagreb index of a connected graph can be any positive integer, except 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 26, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 41, 42, 43, 44, 45, 46, 47, 49, 50, 51, 52, 53, 54, 55, 57, 59, 60, 61, 62, 63, 65, 66, 67, 68, 69, 70, 71, 73, 75, 76, 77, 78, 79, 81, 82, 83, 84, 85, 86, 87, 91, 92, 93, 94, 95, 98, 99, 100, 101, 102, 103, 107, 109, 110, 111, 114, 115, 118, 119, 123, 126, 127, 130, 131, 133, 134, 135, 141, 142, 143, 146, 147, 149, 150, 151, 157, 158, 159, 163, 165, 167, 173, 174, 175, 181, 183, 190, 191, 199, 206, 215, 222, 223, 231, 239, 255, and 271.Proof.
We construct a series of sixteen graphs such asH0,H1,H2,…,H15. The HM2 values of these graphs can be expressed in the form 16h+i for i=0,1,2,…,15. In Figure 7, we construct the graphs Hk for k=2,3,4,5,6,7 and 11,12,13,14,15. Note that the graphs H0,H1,H8,H9,H10 are similar to Figures 4(a), 4(f), 4(c), 4(h), and 4(g) respectively. We have HM2 (H0) = 48. Then by using Lemma 3, we can take the graphs with HM2 values 64, 80, 96, 112, … which are congruent to 0 (mod 16). Secondly, consider the graph H1 which generates the HM2-values 97,113,129,145,161,…, and all these are congruent to 1 (mod 16).
SinceHM2(H2) = 162, by mean of the construction method upon the graph H2 from the Lemma 3, we get the graphs with HM2 values 178, 194, 210,226, … which are congruent to 2 (mod 16). For H3, the HM2-values cover the integers 179,195,211,227,… which are ≡3 (mod 16). Analogously, the HM2 values for the graph H4 cover all the integers 116,132,148,…., and all these numbers are congruent to 4 (mod 16). For H5, it provides the HM2 values 197,213,229,… which are ≡5 (mod 16). For H6 there exist HM2 values 166,182,198,… which are ≡6 (mod 16). It follows 247,263,379,… for the graph H7, and these integers are congruent to 7 (mod 16). Similarly by Lemma 3, we get for the graphs H8,H9,H10,H11,H12,H13,H14,H15 with Now, using the construction method in Lemma 3 to H8,H9,H10,H11,H12,H13,H14, and H15, we can generate the graphs with HM2 values 8, 24, 40, … congruent to 8 (mod 16); 89, 105, 121, … congruent to 9 (mod 16); 58, 74, 90, … congruent to 10 (mod 16); 139, 155, 171, … congruent to 11 (mod 16); 108, 124, 140, … congruent to 12 (mod 16); 189, 205, 221, … congruent to 13 (mod 16); 238, 254, 270, … congruent to 14 (mod 16); and 257, 303, 319, … congruent to 15 (mod 16), respectively.
The examples drawn in the Figures2(c), 2(d), 5(a), and 5(b) have HM2 values 117,27,125, and 207, respectively. These numbers are congruent to 5,11,13, and 15 (mod 16), chronologically. There exist no connected graphs with the HM2-indices mentioned in Table 4.Figure 7
The graphsHk, for k = 2, 3, 4, 5, 6, 7 and 11, 12, 13, 14, 15.Table 4
HM2 values which do not exist.
H0H1H2H3H4H5H6H7H9H10H11H12H13H14H152345679101112131415161718192021222325262829303132333435363738394142434445464749505152535455575960616263656667686970717375767778798182838485868791929394959899100101102103107109110111114115118119123126127130131133134135141142143146147149150151157158159163165167173174175181183190191199206223, 239215, 231222255, 271Corollary 5.
The second hyper-Zagreb index of a tree (or molecular) graph can be any positive integer, except 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 26, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 41, 42, 43, 44, 45, 46, 47, 49, 50, 51, 52, 53, 54, 55, 57, 59, 60, 61, 62, 63, 65, 66, 67, 68, 69, 70, 71, 73, 75, 76, 77, 78, 79, 81, 82, 83, 84, 85, 86, 87, 91, 92, 93, 94, 95, 98, 99, 100, 101, 102, 103, 107, 109, 110, 111, 114, 115, 118, 119, 123, 126, 127, 130, 131, 133, 134, 135, 141, 142, 143, 146, 147, 149, 150, 151, 157, 158, 159, 163, 165, 167, 173, 174, 175, 181, 183, 190, 191, 199, 206, 215, 222, 223, 231, 239, 255, and 271.


## 3.4. The IP for Reformulated First Zagreb Index

Theorem 5.
The first reformulated Zagreb index of a connected graph can take all positive even integer values except for 4 and 8.Proof.
At first, we consider the pathPn with n≥3. The Rez-value for P3 is equal to 2. By Lemma 4, we obtain graphs with Rez-values 6, 10, 14, 18, …, and so on. Also, since RezS3=12, by means of the construction described in Lemma 4, we have the graphs whose Rez-values are 16, 20, 24, 28, 32, 36, 40, …. Hence, RezŁ covers all positive even integers except 4 and 8.Corollary 6.
The first reformulated Zagreb index of a tree (or molecular) graph can take all positive even integer values, except for 4 and 8.


## 3.5. The IP for ReformulatedF-Index

Theorem 6.
The reformulatedF-index of a connected graph can be any positive even integer, except for 4, 6, 8, 12, 14, 16, 20, 22, 28, 30, 36, 38, 46, 54, and 62.Proof.
For the path graphsP3, we get RFP3=2. Thus, by applying Lemma 4, we obtain graphs with RFŁ-values equal to 10, 18, 26, 34, …. Similarly, for the cyclic graph C3, we have RFC3=24 and next obtained graphs having RFŁ-values 32, 40, 48, 56, …. In an analogous manner, starting with G5 and G6 in Figure 4, we obtain the graphs with RF-values 78, 86, 94, 102, … and 52, 60, 68, 76, …, respectively.Corollary 7.
The reformulatedF-index of a tree (or molecular) graph can be any positive even integer, except for 4, 6, 8, 12, 14, 16, 20, 22, 28, 30, 36, 38, 46, 54, and 62.


## 4. Conclusion

The inverse problem is one of the recent problems of graph theory related to the applicative area. Here, we have studied the IP based on some topological graph indices such asY-index, Gourava indices, second hyper-Zagreb index, reformulated first Zagreb index, and reformulated F-index. We have studied the inverse problems for the aforesaid indices since they are closely related to each other. We have also investigated the results for tree, molecular, unicyclic, and bicyclic graphs. The inverse problem is still open for other graph indices and other molecular structures.



---

*Source: 9411696-2021-11-30.xml*