# On Some Structural Properties of Integer-Based Graphs and Their Topological Indices

Authors: Faqir M. Bhatti; Muhammad Malooq; Jihad Ahmad; Iqra Zaman; Muhammad Usman
Journal: Journal of Mathematics
 (2022)

---

## Abstract

Integer partition plays an important role in different fields like graph theory and number theory. This paper comprises different properties of the integer partition-based graphs. These properties give an idea about the structural properties like degree of the vertices. Furthermore, topological index of the graphs is considered as a transformation of a chemical structure into an integer number. We discussed two very important indices, namely, harmonic index and Randic index, for these particular graphs.


---

## Body

## 1. Introduction

Graph theory [1] has a major impact on different major fields, one of them being topological indices in chemical-based experiments [2]. Cheminformatics is a mix of science, mathematics, and information science. It inspects quantitative design-development (QSAR) and structure-property (QSPR) associations that are used to anticipate the natural activities and properties of substance blends [3]. Randic index and harmonic index, among other topological records, are utilised in the QSAR or QSPR investigation to predict the bioactivity of the engineered balances [4]. Molecular structure is a depiction of the helper condition of an compound with respect to structural speculation, whose vertices contrast with the bits of the compound and edges identify with substance bonds. A structure GX,Y with vertex set X and edge set Y is related, if there happens to be an affiliation between any pair of vertices in G. A structure of graph is essentially a related outline having no different edges and no cycles. We can define some famous indices of graphs, and one of the famous and deep-rooted topological indices is the Randic index [5] defined by Millan Randic in 1975 [4] as(1)R=RG=∑x∼y1dxG⋅dyG,where x∼y is an edge between vertices and dxG and dyG represent the degree of vertices x and y, respectively. After the success of the Randic index, researchers began working on the harmonic index and published several papers [4]. During the 1980s, Siemion Fajtlowicz [5] made a PC program for the programmed generation of guesses in graph theory. Then, he inspected the potential relations between incalculable graph invariants, between which there was a vertex-degree-based amount, which is defined in [6] as(2)HG=∑x∼y2dxG⋅dyG.Integer partition is a very useful area which has many applications in different fields like encryption and cryptography in data mining [7] and in Ising spin glass in physics [8]. Studies of integer partitions utilize the approach of statistical mechanics in ensembling quantum particles [9–14]. The connection between a physical problem and integer partitions was first noted by Bohr and Kalckar in 1937 [15] with respect to the calculation of the density of energy levels in heavy nuclei. In the same year, Lier and Uhlenbeck noted the links between counting microstates of the systems obeying Bose or Fermi statistics and some integer partition problems [16]. In this paper, we study some results on structural properties of the graphs discussed in [17], and these graphs are constructed by using integer partitions [18] and Young diagrams; a typical structure is given in Figure 1.Figure 1
Integer-based graph for integer 5.


## 2. Main Result

The aim of this section is to work out on some topological indices of integer-based graph. First, we discuss some symbols and definitions, which are helpful to prove the results. Letn be a positive integer and 1n represent the sum of 1′s for n time, i.e., 1+1+1+1+⋯+1. If n=5, then 15=1+1+1+1+1. Let n be a positive integer; then, ∧ represents the sequence of x such that(3)∧i=2n−1xi=x2,x3,x4…xn−1.Theorem 1.
LetGnX,Y be an integer-based graph; then, the number of vertices with degree one, Vd1, is(4)NGn;Vd1=n1,∧i=2n−1ij,1n,where j=n/2 and(5)∧i=2n−1ij=2j,3j,4j,5j,…,n−1j.
Also,in/2<n, n/2<i, and n/2 is always an integer.Proof.
LetGn be an integer-based graph, and the positions of the total number of vertices with degree one are shown in Figure 2. By using the sequence from the upper layer of the graph, we get the position of vertices in the graph which has exactly degree one as shown in Figure 3. By using the sequence, we get(6)⇒n1,2j,3j,4j,5j…n−1j,1n,⇒n1,∧i=2n−1in/2,1n=NGn;Vd1.
This completes the proof.Figure 2
Position of vertices of degree one in integer-based graph.Figure 3
Position of vertices of degree one in Figure2.Theorem 2.
LetGnp be an integer-based graph with any prime integer n; then, there exist exactly two vertices with degree one, such that(7)NGnp;Vd1=n1,1n.Proof.
We prove this theorem by the method of contradiction.Letnbe the prime number; then by using Theorem 1, the total number of vertices with degree one is given as(8)NGn;Vd1=n1,∧i=2n−1in/2,1n.
The prime numbern has two divisors:1 and itself, as is well known. In equation (8), the part ∧i=2n−1in/2 shows that n is not a prime number due to n/2, which is a contradiction. Our supposition is wrong; then, the graph with any prime integer n has exactly two vertices with degree one, i.e.,(9)NGnp;Vd1=n1,1n.
This completes the proof.Theorem 3.
LetGnX,Y be an integer-based graph, and the total number of vertices with degree 3, Vd3, is given as(10)NGn−1;Vd3=∑i=2nNGn;Vd1,where(11)NGn;Vd1=n1,∧i=2n−1ij,1n,and(12)∧i=2,n−1in/2=2n/2,3n/2,4n/2,5n/2…n−1n/2.
There are two conditions for indexi: these are in/2<n and n/2<i; also, n/2 is always an integer.Proof.
LetGnX,Y be an integer-based graph, and the positions of the vertices having degree 3 are shown in Figures 4 and 5. By using Figure 5’s sequence, we get(13)⇒n1,2J,3J,4J,5J…n−1J,1n,⇒n1,∧i=2n−1,1n,=NGn;Vd1.
Forn=2, equation (4) becomes(14)NG2;Vd1=2,1+1=2.
Forn=3,(15)NG3;Vd1=3,1+1+1=2.
Forn=4,(16)NG4;Vd1=4,24/2,34/2,1+1+1=3.
By Theorem1, we ignore the term in/2 when n is odd. By the criteria, we can ignore the term 34/2 because in/2<n and 34/2=6 in equation (7); if we continue this process, we get(17)NGn;Vd1=n1,∧i=2n−1,ij,1n.
By adding allNGi;Vd1 where i=2,3,4,…,n−1, we get(18)NG2;Vd1+NG3;Vd1+NG4;Vd1+NG5;Vd1+⋯+NGn−1;Vd1=∑i=2n−1NGn;Vd1=NGn;Vd3,which is required result. This completes the proof.
Now we will discuss some results on harmonic index and Randic index for the graphsGn.Figure 4
Position of vertices of degree 3.Figure 5
Position of vertices of degree 3 of Figure4.Lemma 1.
LetHG be the harmonic index of graph Gn; then,(19)HGn+1≈HGn+2Pn−Pn+1+1,where Pn is the integer partition of a positive integer.Theorem 4.
LetGn be an integer partition-based graph and Pn be the number of integer partitions of positive integers; then, the harmonic index of graph Gn is given as(20)HGn+1≈∑k=0nPk−Pn+1+ξ,where(21)ξ=0forn=01forn=1n−1forn≥2.Proof.
We prove this theorem by mathematical induction; for the base step, we will start with the initial graphs.
Forn=0, we get(22)HG1=∑k=0Pk−P0+1+0=0.
Now we suppose that statement is true forn=m, and we get(23)HGm+1=∑k=0mPk−Pm+1+m−1.
Now we have to prove that equation (21) is true for n=m+1:(24)HGm+2=∑k=0m+1Pk−Pm+2+m+1−1.
By using Lemma1,(25)HGn+1≈HGn+2Pn−Pn+1+1.
By replacingn=m+1, we get(26)HGm+2≈HGm+1+2Pm+1−Pm+1+1+1HGm+1+2Pm+1−Pm+2+1=∑k=0mPk−Pm+1+m−1+2Pm+1−Pm+2+1=∑k=0mPk+Pm+1−Pm+2+m+1−1=∑k=0m+1Pk−Pm+1+1+m+1−1≈HGm+1+1.
This completes the proof.Theorem 5.
LetRGn be the Randic index of the integer-based graph Gn; then,(27)RGn=∑k=02k≤n+1Pn+1−2k+1,where Pn is the number of partition of positive integer.Proof.
We prove this theorem by the method of contradiction. Let us suppose that the limits are true for2k≤n+1. Now we check for 2k≥n+1.(28)RGn=∑k=02k≥n+1Pn+1−2k+1=Pn+1−20+Pn+1−21+Pn+1−22+⋯+Pn+1−2k+Pn+1−2k+1+1=Pn+Pn−1+Pn−2+⋯+Pn+1−2k+Pn+1−2k+1+1.
In the terms Pn+1−2n,Pn+1−2k+1. If 2k≥n+1then Pn+1−2k, is zero becausen+1−2kis negative. In point of fact, in the statement of the theoremPnis the number of partitions for positive integers. Which is a contradiction. Hence, our supposition is wrong. So, theorem is true for 2k≤n+1. This completes the proof.


## 3. Conclusions

The graphs addressed in this study are entirely based on young diagrams and integer partitions. We compute harmonic and Randic index for these graphs. These indices have a significant influence on the physical and biological properties of molecules. Furthermore, we investigate structurally based property including degrees of specific vertices using corresponding young diagrams.



---

*Source: 5481940-2022-08-21.xml*