Algorithms for Distance-based Topological Indices for Zero Divisor Graphs of Commutative Rings with Primes

Mathematical solutions are sometimes complex to solve mathematically. Algorithms can provide the solution to these problems. Our article introduced algorithms to compute distance-based topological indices for zero divisor graphs containing finite rings as Zp₁p₂ × Zq. and Zp² × Zq, having primes p¹, p², and q. Algorithm results can be reused in standing physical structures, solving computer network problems, and designing mechanics.

Background

Graphs have solved structural problems in the fields of chemistry and biology. They have practically provided the solution for real-time problems [1]. Due to their importance in pure sciences, a new field has been introduced called molecular graph theory. To understand the characteristics of a graph topological indices are used. They can be calculated based on different parameters. If a calculation is based on distances in the graphs, then they are called “Distance-based topological indices” [2,3]. Other known types are “Degree-based topological indices” [4,5].

Topological indexes where calculations are dependent on distances between graph vertices are called “distance-based topological indexes”[6-12]. This index was introduced by Harry Wiener in 1947 [3]. Since then, many other indices of this type have been introduced that have practical applications in different fields such as robotics, computer science, medicine, networks, and physics. Known examples of distance-based topological indices are the Weiner index, Schultz index, modified Schultz index, Hosoya polynomial, and Schultz polynomial [3,13-15,], there are still many difficulties, especially in areas such as zero divisor graphs, that are needed that these indices are further examined and adjusted.

Group and ring theory are linked with practical applications of algebra and number theory. They have been studied and explored for their practical use [16,17]. Group and ring theory consists of many things out of which an important part is finite commutative rings. Finite commutative rings are important in, the analysis of computer algorithms, data modelling, data analysis, the discipline of engineering, graph coding, wireless communications, combinatorics, and coding theory. An important finite commutative ring is a Zero divisor graph [16,18].

Algorithmic solutions are used to solve complex and mathematically insolvable problems. Now, a number of algorithms are available in almost all branches of science to deal with complex practical problems [11]. They are like road maps for accomplishing a given, well-defined task in an accurate and efficient way. Some famous algorithmic techniques are Brute Force, Greedy Algorithms, Divide-and-Conquer, Dynamic Programming, Genetic Algorithms, etc. In this paper, we will create an algorithm that will calculate distance-based topological indices for zero divisor graphs having commutative rings with three primes a, b, and c.

Distance-based topological indices

If G is a connected graph having vertex set V (G) and edge set E(G), respectively. The d (u, v) is the distance between vertex u and vertex v, which is the shortest path between vertices u and v. The distance-based topological indices have played an important role in understanding the distance characteristics of the graphs.

$w={\displaystyle \sum _{uv\in V(G)}d(u,v)}\text{ (1)}$

Hosoya Polynomial of G is given as [10];

$H={\displaystyle \sum _{uv\in V(G)}{x}^{d(u,v)}}$

They have provided practical solutions for distance-based problems like vertex-to-vertex distance, shortest routes, etc. The d(v) is the degree of vertex v. Wiener index introduced by Harry Wiener in 1947 [3] is given as:

Understanding the characteristics of a graph helps us in solving complex problems. We can find out their characteristics with the help of topological indices. A special type of topological index is the "Distanced-based topological index", have practical applications in robotics, physics, computer science, and other areas of science. If A is a commutative ring, and if P(A) is a set of all zero divisors in A. If u.v=0 , where u, v ∈ V (G(A)) = P(A) and (u, v) ∈ E(P(A)), then G(A) is a zero divisor graph [17,18]. Different authors have studied commutative rings, and zero-divisor graphs [16,19-24].

Algorithmic approach

Schultz index is given as [15];

$S={\displaystyle \sum _{uv\in V(G)}\{d(u)+}d(v)\}d(u,v)\text{ (3)}$

Modified Schultz index is given as [25];

$S^{*}={\displaystyle \sum _{uv\in V(G)}\{d(u)\times }d(v)\}d(u,v)\text{ (4)}$

We need a proper way to solve the problems. Algorithms provide us with the steps and a proper approach for finding solutions. Nowadays, mathematical problems have algorithmic solutions [26]. Algorithms provide numerical complex calculations. Once, a developed algorithm can be used further in the future for similar types of problems. Sometimes an algorithm used previously developed algorithms for the next step enhances problems. Algorithms convert inputs into the required solution or outputs. They are helpful in data processing, route findings, mathematical operations, and logical solutions in computer science [26].

This article focuses on developing a program to calculate distance-dependent topological indices by constructing zero divisor graphs with finite rings: Zp₁p₂ × Zq and Zp² × Zq [22]. These algorithms require three prime numbers as input and compute the Wiener index, Hosoya polynomial, Schultz index, and modified Schultz index for zero divisor graphs. Algorithms must be designed carefully, to get accurate results and efficient solutions.

In a zero-divisor graph, there are two different cases of a commutative ring with three primes, denoted as a, b, c: Zp² × Zq and Z_{p1p2 × Zq [27]. In the first case, [27], a and b represent the same primes, and in the second case, a, b, and c are different prime numbers. The algorithm is designed to intelligently handle both cases and calculate indices accordingly [27].}

Algorithm

Input: Numbers d, e, and f.

Output: Generate Parameters for distance-based topological indices.

-------------------------------------------------

Function calculateParamters(d,e,f)

-------------------------------------------------

1: for v ← 0 to d × e

2:     for u ← 0 to f

3:        if (v/= 0 OR u /= 0)

4:         if (d /= e)

5:                if (v mod d /= 0 AND v mod e /= 0 AND v /= 0 AND u = 0)

6:                     V 4[di] ← AddPoint(v,u)

7:                else if (v= 0 AND u /= 0)

8:                     V 1[ai] ← AddPoint(v,u)

9:                else if (v mod d = 0)

10:                      if (u = 0)

11:                          V 2[bi] ← AddPoint(v,u)

12:                      else

13:                          V 5[ei] ← AddPoint(v,u)

14:                else if (vmod e = 0)

15:                     if (u /= 0)

16:                          V 6[fvi] ← AddPoint(v, u)

17:                     else

18:                          V 3[ci] ← AddPoint(v,u)

19:         else

20:                if (v mod d /= 0 AND v /= 0 AND u = 0)

21:                     V 4[di] ← AddPoint(v,u)

22:                else if (v = 0 AND u /= 0)

23:                     V 1[ai] ← AddPoint(v,u)

24:                else if (v mod d = 0)

25:                     if (u = 0)

26:                          V 2[bi] ← AddPoint(v, u)

27:                     else

28:                          V 3[ci] ← AddPoint(v,ju)

29: if (d /= e)

30:           SumDistance1 ← ai × bi + ai × ci + ai × di + bi × ci + bi × fi+ ci × ei 31:        SumDistance2 ← ai × fi+ ai × ei + bi × di + bi × ei + ci × di + ci × fi 32: DistanceDegree2 ← ai × fi(a × b − 1 + b − 1) + ai × ei(a × b − 1 + a − 1)

33:                 +bi × di(a × c − 1 + c − 1) + bi × ei(a × c − 1 + a − 1)

34:                 +ci × di(b × c − 1 + c − 1) + ci × fi(b × c − 1 + c − 1)

35:           DegreeProduct2 ← ai × fi((a × b − 1) × (b − 1)) + ai × ei((a × b − 1) × (a − 1))

36:                 +bi × di((a × c − 1) × (c − 1)) + bi × ei((a × c − 1) × (a − 1))

37:                 +ci × di((b × c − 1) × (c − 1)) + ci × fi((b × c − 1) × (c − 1))

38:          SumDistance3 ← di × ei + di × fi+ ei × fi

39:           DistanceDegree3 ← di × ei(c − 1 + a − 1) + di × fi(c − 1 + b − 1) + ei × fi(a − 1 + b − 1)

40:           DegreeProduct3 ← di × ei((c − 1) × (a − 1)) + di × fi((c − 1) × (b − 1))

41:                          +ei × fi((a − 1) × (b − 1))

42: else

43:           SumDistance1 ← ai × bi + ai × di + bi × ci

44:           SumDistance2 ← ai × ci + bi × di

45:           DistanceDegree2 ← ai × ci(a × a − 1 + a − 1) + bi × di(c − 1 + a × c − 2

46:           DegreeProduct2 ← ai × ci((a × a − 1) × (a − 1)) + bi × di((c − 1) × (a × c − 2)

47:           SumDistance3 ← ci × di                 

48:           DistanceDegree3 ← ci × di(c − 1 + p − 1)

49:           DistanceProduct3 ← ci × di((c − 1) × (p − 1))

50: return SumDistance1, SumDistance2, SumDistance3, DistanceDegree2,

51:               DistanceDegree3,DegreeProduct2,DegreeProduct2

-------------------------------------------------

Input: Prime numbers x, y and z.

Output: Distance-based Topological indices.

Main Algorithm calculateIndices(z,y,z)

1: calculateParamters(x, y, z)

2: WinnerIndex ← SumDistance1 + SumDistance2 + SumDistance3

3: Hosoya ← xSumDistance1+SumDistance2+SumDistance3

4: Schultz ← SumDistance1 + 2 × DistanceDegree2 + 3 × DistanceDegree3

5: M odif iedSchultz ← SumDistance1 + 2 × DegreeProduct2 + 3 × DegreeProduct3

6: return WinnerIndex, Hosoya, Schultz, ModifiedSchultz

-------------------------------------------------

Algorithm results

The computer-based experiments have been conducted in which a number of zero divisor graphs have been generated for different prime numbers p₁, p₂, and q (Table 1). Distance-based topological indices Weiner Index, Hosoya Polynomial, Schultz Index, and Modified Schultz Index are computed from the algorithm for the graphs and results have been verified mathematically. Figure 1 shows one of the outcomes of the algorithm. After generating different graphs, we can find general vertex sets and characteristics of zero divisor graph, as shown in Figure 2. Our algorithm further computed the mentioned distance-based topological indices, which have been verified mathematically.

Figure 1: Computer experiment outcome.

Figure 2: Groups of vertex sets and distances obtain from computer experiment.

Conclusion

The findings of the research are helpful for the fields of Mathematics and Computer Science. It computes distance-based topological indices for zero divisor graphs containing commutative rings Z_p1_p2×Z_q and Z_p2×Z_q algorithmically. These results are quite significant due to the dynamic size of graphs, by using an algorithmic approach. Results give a comparison between different indices on a zero divisor graph as shown in Figure 3, also the results can be compared with other graph families. Secondly, the algorithm can be further modified to find the shortest path between vertices. The given algorithm is valid for any size of the graph as long as resources of computer supports, and its output can be used in under- standing physical structures (cylindrical fullerenes, hexagonal chains, silicone, polymers), solving problems in computer networks, and physical designs of mechanics.

Figure 3: Trend Comparison of Topological Indices 1.

1. Gutman I. Selected properties of the Wiener polynomials. Graph Theory Notes New York. 1993;25:13-18.
2. Dobrynin AA, Entringer R, Gutman I. Wiener index of trees: theory and applications. Acta Appl Math. 2001;66:211–249. Available from: https://link.springer.com/article/10.1023/a:1010767517079
3. Wiener H. Structural determination of paraffin boiling points. J Am Chem Soc. 1947;69:17-20. Available from: https://pubs.acs.org/doi/pdf/10.1021/ja01193a005
4. Ba˘ca M, Horvrathova J, Mokriˇsova M, Suhanyiov`a A. On topological indices of fullerenes. Appl Math Comput. 2015;251:154–161. Available from: https://doi.org/10.1016/j.amc.2014.11.069
5. Baig AQ, Imran M, Ali H, Rehman SU. Computing topological polynomial of certain nanostructures. J Optoelectron Adv Mater. 2015;17(5-6):877–883. Available from: https://www.researchgate.net/publication/279749117_Computing_topological_polynomials_of_certain_nanostructures
6. Basak SC, Magnuson VR, Niemi GJ, Regal RR, Veith GD. Topological indices: their nature, mutual relatedness, and applications. Math Modell. 1987;8:300-305. Available from: https://doi.org/10.1016/0270-0255(87)90594-X
7. Hayat S, Imran M. On some degree based topological indices of certain nanotubes. J Comput Theor Nanosci. 2015;12(8):1599–1605. Available from: https://doi.org/10.1166/jctn.2015.3935
8. Hayat S, Imran M. Computation of topological indices of certain networks. Appl Math Comput. 2014;240:213–228. Available from: https://doi.org/10.1016/j.amc.2014.04.091
9. Liu B, Gutman I. Estimating the Zagreb and the general Randic indices. Commun Math Comput Chem. 2007;57:617–632. Available from: https://match.pmf.kg.ac.rs/electronic_versions/Match57/n3/match57n3_617-632.pdf
10. Matejic M, Milovanovic I, Milovanovic EI. On bounds for harmonic topological index. Filomat. 2018;32(1):311-317. Available from: http://dx.doi.org/10.2298/FIL1801311M
11. Vukiˇcevi´c D, Graovac A. Note on the comparison of the first and second normalized Zagreb eccentricity indices. Acta Chim Slov. 2010;57:524-528. Available from: https://acta-arhiv.chem-soc.si/57/57-3-524.pdf
12. Wang S, Farahani MR, Kanna MRR, Jamil MK, Kumar R.P. The Wiener index and the Hosoya polynomial of the Jahangir graphs. Appl Comput Math. 2016;5(3):138-141. Available from: https://doi.org/10.11648/j.acm.20160503.17
13. Xinmei L, Qian Z. The expected values for the Gutman index and Schultz index in the random regular polygonal chains. Molecules. 2022;27(20):6838. Available from: https://doi.org/10.3390/molecules27206838              
14. Schultz HP. Topological organic chemistry 1. Graph theory and topological indices of alkanes. J Chem Inform Comput Sci. 1989;29:227-228. Available from: https://pubs.acs.org/doi/pdf/10.1021/ci00063a012
15. Klavˇzar S, Gutman I. Wiener number of vertex-weighted graphs and a chemical application. Disc Appl Math. 1997;80:73–81. Available from: https://doi.org/10.1016/S0166-218X(97)00070-X
16. Asir T, Tamizh Chelvam T. On the total graph and its complement of a commutative ring. Comm Algebra. 2013;41(10):3820–3835. Available from: https://doi.org/10.1080/00927872.2012.678956
17. Beck I. Coloring of a commutative ring. J Algebra. 1988;116:208-226. Available from: https://doi.org/10.1016/0021-8693(88)90202-5
18. Anderson DF, Livingston PS. The zero-divisor graph of commutative ring. J Algebra. 1999;217:434–447.
19. Ahmad A, Haider A. Computing the radio labeling associated with zero divisor graph of a commutative ring. U.P.B. Sci. Bull., Series A. 2019;81(1):65–72. Available from: https://www.scientificbulletin.upb.ro/rev_docs_arhiva/reze3e_408258.pdf
20. Anderson DF, Axtell MC, Stickles JA Jr. The zero-divisor graphs in commutative ring. J Algebra. 2011;217(2):434–447. Available from: https://link.springer.com/chapter/10.1007/978-1-4419-6990-3_2
21. Anderson DF, Mulay SB. On the diameter and girth of a zero-divisor graph. J Pure Appl Algebra. 2008;210(2):543–550. Available from: https://doi.org/10.1016/j.jpaa.2006.10.007
22. Rayer CJ, Jeyaraj RS. Applications on topological indices of zero-divisor graph associated with commutative rings. Adv Combin Graph Theory. 2023;15(2):335. Available from: https://doi.org/10.3390/sym15020335
23. Backhouse R. Principles of algorithmic problem solving. Wiley; 2012.
24. Elahi K, Ahmad A, Hasni R. Construction algorithm for zero divisor graphs of finite commutative rings and their vertex-based eccentric topological indices. Mathematics. 2018;6(12):301. Available from: https://doi.org/10.3390/math6120301
25. Todeschini R, Consonni V. Handbook of Molecular Descriptors. Weinheim: Wiley VCH; 2000. Available from: https://download.e-bookshelf.de/download/0000/6031/40/L-G-0000603140-0002364944.pdf
26. Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to algorithms. 3rd ed. Cambridge (MA): The MIT Press; 2009. Available from: https://cdn.manesht.ir/19908___Introduction%20to%20Algorithms.pdf
27. Elahi K, Ahmad A, Asim MA, Hasni R. Computation of edge-based topological indices for zero divisor graphs of commutative rings. Ital J Pure Appl Math. 2022;48:523-534. Available from: https://ijpam.uniud.it/online_issue/202248/40%20Elahi-Ahmad-Asim-Hasni.pdf