Open Access
ARTICLE
On Some Ev-Degree and Ve-Degree Dependent Indices of Benes Network and Its Derived Classes
1 School of Software, Pingdingshan University, Pingdingshan, China
2 College of Computing and Information Technologies, National University, Manila, Philippines
3 Henan International Joint Laboratory for Multidimensional Topology and Carcinogenic Characteristics Analysis of Atmospheric Particulate Matter PM2.5, Pingdingshan, China
4 Centre for Advanced Studies in Pure and Applied Mathematics, Bahauddin Zakariya University, Multan, Pakistan
* Corresponding Authors: Asfand Fahad. Email: ,
(This article belongs to the Special Issue: New Aspects of Computational Algorithms of Graphical Network in Fixed Point Theory)
Computer Modeling in Engineering & Sciences 2023, 135(2), 1685-1699. https://doi.org/10.32604/cmes.2022.023563
Received 02 May 2022; Accepted 07 July 2022; Issue published 27 October 2022
Abstract
One of the most recent developments in the field of graph theory is the analysis of networks such as Butterfly networks, Benes networks, Interconnection networks, and David-derived networks using graph theoretic parameters. The topological indices (TIs) have been widely used as graph invariants among various graph theoretic tools. Quantitative structure activity relationships (QSAR) and quantitative structure property relationships (QSPR) need the use of TIs. Different structure-based parameters, such as the degree and distance of vertices in graphs, contribute to the determination of the values of TIs. Among other recently introduced novelties, the classes of ev-degree and ve-degree dependent TIs have been extensively explored for various graph families. The current research focuses on the development of formulae for different ev-degree and ve-degree dependent TIs for dimensional Benes network and certain networks derived from it. In the end, a comparison between the values of the TIs for these networks has been presented through graphical tools.Keywords
A classic and helpful strategy is to attach various graphs to objects that may be an algebraic structure, a chemical structure of a drug, or a network, which assists in understanding certain features of the objects. Various graph parameters can be associated with the properties of the structure under examination which leads to a deeper study of its theory. These properties may include the algebraic properties of the zero divisor graphs and the physio chemical properties of the chemical structures. By adopting this strategy, several researchers studied different objects such as algebraic objects [1], pysio-chemical properties of chemical structures [2–4], drugs used for breast cancer treatment [5], and interconnection networks [6]. The analysis of networks, such as Butterfly network [7], Benes network [8,9], Interconnection network [6,10] and David-derived network [11] through similar approach, is one of the most recent developments in the field of graph theory.
The class of topological indices (TIs) is a significant class of parameters associated with graphs. Many TIs have been introduced and studied during the last fifty years. Among the class of degree dependent TIs, the Zagreb indices (ZIs) introduced in [12], vastly studied due to the ability to estimate the
Butterfly graphs are the associated graphs of Fast Fourier Transforms (FFT) networks which are especially effective in performing the FFT. The butterfly network is constructed by a sequence of switch stages and connector patterns that allow ′n′ different configurations. The ′n′ outputs should be connected to ′n′ inputs. Furthermore, the Benes network obtained by attaching back-to-back butterfly networks is known for permutation routing [8]. These networks are key multistage interconnection networks with appealing communication network topologies [9]. The graph associated to s-dimensional butterfly network consists of vertex set V with elements [v, i] in which v is an s-bit binary number representing the row of the node and
Let G(V,E) denotes a connected graph having V as a vertex set and E as an edge set. For
3 Ev-Degree Dependent Topological Indices for Bensen Networks and Its Derived Classes
In this section, we prove analytical formulae for the ev-degree dependent TIs for B(s), VCB(s) and HCB(s). The formulae have been established through partition of the vertex sets of B(s), VCB(s) and HCB(s) on the basis of ev-degree as shown in Tables 2–4. We start with the following theorem for B(s).
Theorem 3.1. For an s-dimensional Benes network B(s), we have:
(i)
(ii)
Proof.
By using Table 2, we compute the ev-degree based indices for Benes network as follows:
(i)
(ii)
Now, we continue to prove the ev-degree dependent TIs for VCB(s) in the next theorem.
Theorem 3.2. For VCB(s), the
(i)
(ii)
Proof. (i) From Table 3 and the definition of
(ii) From Table 3 and the definition of
We conclude the results of this section by proving the ev-degree dependent TIs for HCB(s):
Theorem 3.3. For HCB(s), the
(i)
(ii)
Proof. (i) From Table 4 and the definition of
which upon simplification gives the required result.
(ii) From Table 4 and the definition of
which upon simplification gives the required result.
Now, we present an example of the results proved in this section:
Example 3.1. By taking
4 Ve-Degree Dependent Topological Indices for Bensen Networks and Its Derived Classes
In this section, we develop formulae for the ve-degree dependent TIs for B(s), VCB(s) and HCB(s). The key to obtaining these formulae is to obtain partition the edge set of B(s), VCB(s) and HCB(s) on the basis of ve-degrees of the end vertices of each edge as shown in Tables 6–8.
Theorem 4.1. For B(s), the ve-degree dependent TIs
(i)
(ii)
(iii)
(iv)
(v)
(vi)
(vii)
(viii)
Proof. (i) From Table 6 and the definition of
which upon simplification gives the required formula.
(ii) The Table 6 and the formula for
(iii) The Table 6 and the formula for
(iv) The Table 6 and the formula for
(v) The Table 6 and the formula for
(vi) The Table 6 and the formula for
(vii) The Table 6 and the formula for
(viii) Lastly, the Table 6 and the formula for
which upon simplification gives the required formula.
By using the Table 7 and the formulae of TIs defined in Table 1, we get the following results for the VCB(s).
Theorem 4.2. For VCB(s), ve-degree dependent TIs
(i)
(ii)
(iii)
(iv)
(v)
(vi)
(vii)
(viii)
By using the Table 8 and the formulae of TIs defined in Table 1, we get the following results for the HCB(s).
Theorem 4.3. For HCB(s), the ve-degree dependent TIs
(i)
(ii)
(iii)
(iv)
(v)
(vi)
(vii)
(viii)
Now, we conclude the section by including the following example:
Example 4.1. By taking
We proceed further with our obtained formulae in previous section to study graphical patterns in the values of TIs of B(s), HCB(s) and HCB(s). In Figs. 4–6, the patterns of ZI(VE), RI(VE), ABC-I(VE), GA-(VE) and HI(VE) (on y-axis), where the value of s has been taken on x-axis, for B(s), HCB(s) and VCB(s) have been presented. All the figures show the rapid rise in the values of each TI for B(s), HCB(s) and HCB(s) with the rise in the value of s. The trends in Fig. 4 (L) show that the HCB(s) attains higher values of ZI(VE), whereas values of ZI(VE) for VCB(s) remain between B(s) and HCB(s). Similar trend for RI(VE) has been shown in Fig. 4 (R). In Fig. 5 (L), it can be seen that the values of ABC-I(VE) show different behaviours as in case of ZI(VE) and RI(VE). The ABC-I(VE) attains lowest values for HCB(s), whereas values for B(s) remain between VCB(s) and HCB(s). Furthermore, the trend for HI(EV) is shown in Fig. 5 (R). In the case of GA(VE), the values for B(s) remain the highest and the values for VCB(s) remain between the values of B(s) and HCB(s), see Fig. 6.
The study of newly formed networks is always a fascinating topic. Using B(s), several novel networks such as HCB(s) and VCB(s) have been defined through identifications in [33] and further investigated in [34]. Furthermore, the ev-degree and the ve-degree of these structures were not investigated yet. In the current work, we constructed the ev-degree based partition of the vertex set and the ve-degree based partition of the edge set for these networks. Through these partitions, we developed formulae for several ev-degree and ve-degree based TIs for B(s), HCB(s) and VCB(s) in terms of the parameter s. Further, we presented the comparative analysis of the values of ZI(VE), RI(VE), ABC-I(VE), GA-I(VE) and HI(VE) for B(s), HCB(s) and VCB(s). It is observed that similar patterns have been developed for ZI(VE) and RI(VE), whereas the other three TIs produce different trends.
Acknowledgement: The authors are thankful to their respective institutes.
Funding Statement: This work is partially supported by the National Natural Science Foundation of China (Grant No. 61702291); China Henan International Joint Laboratory for Multidimensional Topology and Carcinogenic Characteristics Analysis of Atmospheric Particulate Matter PM2.5.
Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.
References
1. Selvakumar, K., Gangaeswari, P., Arunkumar, G. (2022). The wiener index of the zero-divisor graph of a finite commutative ring with unity. Discrete Applied Mathematics, 311, 72–84. DOI 10.1016/j.dam.2022.01.012. [Google Scholar] [CrossRef]
2. Yang, Y., Liu, H., Wang, H., Fu, H. (2015). Subtrees of spiro and polyphenyl hexagonal chains. Applied Mathematics and Computation, 268, 547–560. DOI 10.1016/j.amc.2015.06.094. [Google Scholar] [CrossRef]
3. Oz, M. S., Cangul, I. N. (2022). Enumeration of independent sets in benzenoid chains. MATCH Communications in Mathematical and in Computer Chemistry, 88, 93–107. DOI 10.46793/match.88-1.093o. [Google Scholar] [CrossRef]
4. Yang, Y., Sun, X. J., Cao, J. Y., Wang, H., Zhang, X. D. (2020). The expected subtree number index in random polyphenylene and spiro chains. Discrete Applied Mathematics, 285, 483–492. DOI 10.1016/j.dam.2020.06.013. [Google Scholar] [CrossRef]
5. Bokhary, S. A. U. H., Adnan, Siddiqui, M. K., Cancan, M. (2021). On topological indices and qspr analysis of drugs used for the treatment of breast cancer. Polycyclic Aromatic Compounds. DOI 10.1080/10406638.2021.1977353. [Google Scholar] [CrossRef]
6. Imran, M., Hayat, S., Mailk, M. Y. H. (2014). On topological indices of certain interconnection networks. Applied Mathematics and Computation, 244, 936–951. DOI 10.1016/j.amc.2014.07.064. [Google Scholar] [CrossRef]
7. Liu, X. C., Gu, Q. P. (2002). Multicasts on wdm all-optical butterfly networks. Journal of Information Science and Engineering, 18(6), 1049–1058. [Google Scholar]
8. Beneš, V. E. (1965). Mathematical theory of connecting networks and telephone traffic. New York: Academic Press. [Google Scholar]
9. Manuel, P. D., Abd-El-Barr, M. I., Rajasingh, I., Rajan, B. (2008). An efficient representation of benes networks and its applications. Journal of Discrete Algorithms, 6(1), 11–19. DOI 10.1016/j.jda.2006.08.003. [Google Scholar] [CrossRef]
10. Xu, J. (2013). Topological structure and analysis of interconnection networks. New York: Springer. [Google Scholar]
11. Imran, M., Baig, A. Q., Ali, H. (2016). On topological properties of dominating david derived networks. Canadian Journal of Chemistry, 94(2), 137–148. DOI 10.1139/cjc-2015-0185. [Google Scholar] [CrossRef]
12. Gutman, I., Trinajstić, N. (1972). Graph theory and molecular orbitals. total φ-electron energy of alternant hydrocarbons. Chemical Physics Letters, 17(4), 535–538. DOI 10.1016/0009-2614(72)85099-1. [Google Scholar] [CrossRef]
13. Chen, C., Liu, M., Gu, X., Das, K. C. (2022). Extremal augmented Zagreb index of trees with given numbers of vertices and leaves. Discrete Mathematics, 345(4), 112753. DOI 10.1016/j.disc.2021.112753. [Google Scholar] [CrossRef]
14. Randić, M. (2008). On history of the randić index and emerging hostility toward chemical graph theory. MATCH Communications in Mathematical and in Computer Chemistry, 59(5), 5–124. [Google Scholar]
15. Vukicevic, D., Furtula, B. (2009). Topological index based on the ratios of geometrical and arithmetical means of end-vertex degrees of edges. Journal of Mathematical Chemistry, 46(4), 1369–1376. DOI 10.1007/s10910-009-9520-x. [Google Scholar] [CrossRef]
16. Aouchiche, M., El Hallaoui, I., Hansen, P. (2020). Geometric-arithmetic index and minimum degree of connected graphs. MATCH Communications in Mathematical and in Computer Chemistry, 83, 179–188. [Google Scholar]
17. Estrada, E., Torres, L. A., Rodríguez, L., Gutman, I. (1998). An atom-bond connectivity index: Modelling the enthalpy of formation of alkanes. Indian Journal of Chemistry, 37, 849–855. [Google Scholar]
18. Estrada, E. (2001). Generalization of topological indices. Chemical Physics Letters, 336(3–4), 248–252. DOI 10.1016/S0009-2614(01)00127-0. [Google Scholar] [CrossRef]
19. Das, K. C., Gutman, I., Furtula, B. (2011). On atom-bond connectivity index. Chemical Physics Letters, 511(4–6), 452–454. DOI 10.1016/j.cplett.2011.06.049. [Google Scholar] [CrossRef]
20. Gutman, I., Tošović, J., Radenković, S., Marković, S. (2012). On atom-bond connectivity index and its chemical applicability. Indian Journal of Chemistry, 51, 690–694. [Google Scholar]
21. Zhong, L. (2012). The harmonic index for graphs. Applied Mathematics Letters, 25(3), 561–566. DOI 10.1016/j.aml.2011.09.059. [Google Scholar] [CrossRef]
22. Chellali, M., Haynes, T. W., Hedetniemi, S. T., Lewis, T. M. (2017). On ve-degrees and ev-degrees in graphs. Discrete Mathematics, 340(2), 31–38. DOI 10.1016/j.disc.2016.07.008. [Google Scholar] [CrossRef]
23. Horoldagva, B., Das, K. C., Selenge, T. A. (2019). On ve-degree and ev-degree of graphs. Discrete Optimization, 31, 1–7. DOI 10.1016/j.disopt.2018.07.002. [Google Scholar] [CrossRef]
24. Süleyman, E. (2017). A new tool for qspr researches: Ev-degree randić index. Celal Bayar University Journal of Science, 13(3), 615–618. [Google Scholar]
25. Sahin, B., Ediz, S. (2018). On ev-degree and ve-degree topological indices. Iranian Journal of Mathematical Chemistry, 9(4), 263–277. [Google Scholar]
26. Lee, J. R., Hussain, A., Fahad, A., Raza, A., Qureshi, M. I. et al. (2022). On ev and ve-degree based topological indices of silicon carbides. Computer Modeling in Engineering & Sciences, 130(2), 871–885. DOI 10.32604/cmes.2022.016836. [Google Scholar] [CrossRef]
27. Zahra, N., Ibrahim, M. (2022). A study of ve and ev degree based topological indices of transition metal tetra-cyano benzene structure. Alexandria Engineering Journal, 61(8), 6409–6417. DOI 10.1016/j.aej.2021.12.001. [Google Scholar] [CrossRef]
28. Deepika, T., Lokesha, V. (2020). Computing discrete adriatic indices of probabilistic neural network. European Journal of Pure and Applied Mathematics, 13(5), 1149–1161. DOI 10.29020/nybg.ejpam.v13i5.3712. [Google Scholar] [CrossRef]
29. Ranjini, P., Lokesha, V., Cangül, I. N. (2011). On the Zagreb indices of the line graphs of the subdivision graphs. Applied Mathematics and Computation, 218(3), 699–702. DOI 10.1016/j.amc.2011.03.125. [Google Scholar] [CrossRef]
30. Shwetha Shetty, B., Lokesha, V., Ranjini, P. (2015). On the harmonic index of graph operations. Transactions on Combinatorics, 4(4), 5–14. [Google Scholar]
31. Lokesha, V., Deepika, T., Ranjini, P., Cangul, I. (2017). Operations of nanostructures via, and indices. Applied Mathematics and Nonlinear Sciences, 2(1), 173–180. DOI 10.21042/AMNS.2017.1.00014. [Google Scholar] [CrossRef]
32. Das, K. C., Çevik, A. S., Cangul, I. N., Shang, Y. (2021). On sombor index. Symmetry, 13(1), 140. DOI 10.3390/sym13010140. [Google Scholar] [CrossRef]
33. Hussain, A., Numan, M., Naz, N., Butt, S. I., Aslam, A. et al. (2021). On topological indices for new classes of benes network. Journal of Mathematics, 2021, 6690053. DOI 10.1155/2021/6690053. [Google Scholar] [CrossRef]
34. Wang, W., Nisar, A., Fahad, A., Qureshi, M. I., Alameri, A. (2022). Modified Zagreb connection indices for benes network and related classes. Journal of Mathematics, 2022, 8547332. DOI 10.1155/2022/9347942. [Google Scholar] [CrossRef]
Cite This Article
This work is licensed under a Creative Commons Attribution 4.0 International License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.