Login Register Cart 0
Generic placeholder image

Current Organic Synthesis

Editor-in-Chief

ISSN (Print): 1570-1794
ISSN (Online): 1875-6271

Back
Journal Home About Journal Editorial Board Journal Insight Current Issue Volumes/Issues
Subscribe
Research Article

Omega Indices of Strong and Lexicographic Products of Graphs

Author(s): Medha Itagi Huilgol, Grace Divya D'Souza and Ismail Naci Cangul*

Volume 22, Issue 2, 2025

Published on: 19 April, 2024

Page: [143 - 158] Pages: 16

DOI: 10.2174/0115701794281945240327053046

Price: $65

TIMBC 2025
Abstract

Background: The degree sequence of a graph is the list of its vertex degrees arranged in usually increasing order. Many properties of the graphs realized from a degree sequence can be deduced by means of a recently introduced graph invariant called omega invariant.

Methods: We used the definitions of the considered graph products together with the list of degree sequences of these graph products for some well-know graph classes. Naturally, the vertex degree and edge degree partitions are used. As the main theme of the paper is the omega invariant, we frequently used the definition and fundamental properties of this very new invariant for our calculations. Also, some algebraic properties of these products are deduced in line with some recent publications following the same fashion.

Results: In this paper, we determine the degree sequences of strong and lexicographic products of two graphs and obtain the general form of the degree sequences of both products. We obtain a general formula for the omega invariant of strong and lexicographic products of two graphs. The algebraic structures of strong and lexicographic products are obtained. Moreover, we prove that strong and lexicographic products are not distributive over each other.

Conclusion: We have obtained the general expression for degree sequences of two important products of graphs and a general expression for omega invariants of strong and lexicographic products. Furthermore, we have obtained algebraic structures of strong and lexicographic products in terms of their degree sequences. Also, it has been found that the disruptive property does not hold for strong and lexicographic products.

Keywords: Degree sequence, strong product, lexicographic product, omega index, topological graph index, graph product.

Next »
Graphical Abstract

[1]
West, D.B. Introduction to Graph Theory, 2nd ed; Pearson Education, Inc.: London, United Kingdom, 2001.
[2]
Biswas, P.; Paul, A.; Bhattacharya, P. Analyzing the realization of degree sequence by constructing orthogonally diagonalizable adjacency matrix. Procedia Comput. Sci., 2015, 57, 885-889.
[http://dx.doi.org/10.1016/j.procs.2015.07.501]
[3]
Havel, V. A remark on the existence of finite graph (Hungarian). Casopis Pest. Mat., 1955, 80, 477-480.
[4]
Hakimi, S.L. On the realizability of a set of integers as degrees of the vertices of a graph. J. Soc. Ind. Appl. Math., 1962, 10(3), 496-506.
[http://dx.doi.org/10.1137/0110037]
[5]
Arikati, S.; Maheshwari, A. Realizing degree sequences in parallel. 1994. Available From https://pure.mpg.de/rest/items/item_1857947/component/file_1857946/content
[6]
Seema, Varghese Brinta Babu, An overview on graph products. International Journal of Science and Research Archive, 2023, 10(1), 966-971.
[http://dx.doi.org/10.30574/ijsra.2023.10.1.0848]
[7]
Feder, T. Product graph representations. J. Graph Theory, 1992, 16(5), 467-488.
[http://dx.doi.org/10.1002/jgt.3190160508]
[8]
Imrich, W.; Izbicki, H. Associative products of graphs. Monatsh Math., 1975, 80(4), 277-281.
[http://dx.doi.org/10.1007/BF01472575]
[9]
Kaveh, A.; Rahami, H. A unified method for eigendecomposition of graph products. Commun. Numer. Methods Eng., 2005, 21(7), 377-388.
[http://dx.doi.org/10.1002/cnm.753]
[10]
Lammprey, R.H.; Barnes, B.H. Product of graphs and applications. Model. Simul. (Anaheim), 1974, 5, 1119-1123.
[11]
Puš, V. A remark on distances in products of graphs. Comment. Math. Uni. Carolinae, 1987, 28, 233-239.
[12]
Sabidussi, G. Graph multiplication. Math. Z., 1959, 72(1), 446-457.
[http://dx.doi.org/10.1007/BF01162967]
[13]
Feder, T. Stable networks and product graphs. Mem. Am. Math. Soc, 1995, 116(555), 0.
[http://dx.doi.org/10.1090/memo/0555]
[14]
Huilgol, M.I.; D’Souza, G.D. Codes from k-resolving sets for some product graphs; Preprint, 2024.
[15]
Huilgol, M.I.; D’Souza, G.D. Codes from k-resolving sets for stacked prism graphs; Preprint, 2024.
[16]
Huilgol, M. I.; D'Souza, G. D. Codes from k-resolving sets for some Rook's graphs. Preprint, 2024.
[17]
Ghozati, S.A. A finite automata approach to modeling the cross product of interconnection networks. Math. Comput. Model., 1999, 30(7-8), 185-200.
[http://dx.doi.org/10.1016/S0895-7177(99)00173-9]
[18]
Kaveh, A.; Koohestani, K. Graph products for configuration processing of space structures. Comput. Struc., 2008, 86(11-12), 1219-1231.
[http://dx.doi.org/10.1016/j.compstruc.2007.11.005]
[19]
Kaveh, A.; Nikbakht, M.; Rahami, H. Improved group theoretic method using graph products for the analysis of symmetric-regular structures. Acta Mech., 2010, 210(3-4), 265-289.
[http://dx.doi.org/10.1007/s00707-009-0204-1]
[20]
Kaveh, A.; Rahami, H. An efficient method for decomposition of regular structures using graph products. Int. J. Numer. Methods Eng., 2004, 61(11), 1797-1808.
[http://dx.doi.org/10.1002/nme.1126]
[21]
Nouri, M.; Talatahari, S.; Shamloo, A.S. Graph products and its applications in mathematical formulation of structures. J. Appl. Math., 2012, 2012, 16.
[http://dx.doi.org/10.1155/2012/510180]
[22]
Balasubramanian, K. A generalized wreath product method for the enumeration of stereo and position isomers of polysubstituted organic compounds. Theor. Chim. Acta, 1979, 51(1), 37-54.
[http://dx.doi.org/10.1007/PL00020748]
[23]
Balasubramanian, K. Symmetry groups of chemical graphs. Int. J. Quantum Chem., 1982, 21(2), 411-418.
[http://dx.doi.org/10.1002/qua.560210206]
[24]
De, N. Application of corona product of graphs in computing topological indices of some special chemical graphs.Handbook of Research on Applied Cybernetics and Systems Science; IGI Global: Hershey, Pennsylvania, 2007, pp. 82-101.
[25]
Huilgol, M.I.; Divya, B.; Balasubramanian, K. Distance degree vector and scalar sequences of corona and lexicographic products of graphs with applications to dynamic NMR and dynamics of nonrigid molecules and proteins. Theor. Chem. Acc., 2021, 140(3), 25.
[http://dx.doi.org/10.1007/s00214-021-02719-y]
[26]
Huilgol, M.I.; Sriram, V.; Balasubramanian, K. Tensor and Cartesian products for nanotori, nanotubes and zig–zag polyhex nanotubes and their applications to 13 C NMR spectroscopy. Mol. Phys., 2021, 119(4), e1817594.
[http://dx.doi.org/10.1080/00268976.2020.1817594]
[27]
Pattabiraman, K.; Nagarajan, S.; Chendrasekharan, M. Zagreb indices and coindices of product graphs. Journal of Prime Research in Mathematics, 2015, 10, 80-91.
[28]
Wang, X.; Lin, Z.; Miao, L. Degree-based topological indices of product graphs. Open Journal of Discrete Applied Mathematics, 2021, 4(3), 60-71.
[http://dx.doi.org/10.30538/psrp-odam2021.0064]
[29]
Behzad, M.; Mahmoodian, S.E. On topological invariants of the product of graphs. Can. Math. Bull., 1969, 12(2), 157-166.
[http://dx.doi.org/10.4153/CMB-1969-015-9]
[30]
Bryant, D.E.; El-Zanati, S.I.; Eynden, C.V. Star factorizations of graph products. J. Graph Theory, 2001, 36(2), 59-66.
[http://dx.doi.org/10.1002/1097-0118(200102)36:2<59::AID-JGT1>3.0.CO;2-A]
[31]
Clarke, N.E.; Nowakowski, R.J. A Tandem version of the Cops and Robber Game played on products of graphs. Discuss. Math. Graph Theory, 2005, 25(3), 241-249.
[http://dx.doi.org/10.7151/dmgt.1277]
[32]
Jänicke, S.; Heine, C.; Hellmuth, M.; Stadler, P.F.; Scheuermann, G. Visualization of graph products. IEEE Trans. Vis. Comput. Graph., 2010, 16(6), 1082-1089.
[http://dx.doi.org/10.1109/TVCG.2010.217] [PMID: 20975146]
[33]
Hammack, R.; Imrich, W. Klav, Handbook of product graphs; CRC Press: Boca Raton, 2011.
[http://dx.doi.org/10.1201/b10959]
[34]
Imrich, W. Klav, Product graphs: Structure and Recognition; Wiley- Interscience: New York, 2000.
[35]
Arockiaraj, M.; Clement, J.; Tratnik, N.; Mushtaq, S.; Balasubramanian, K. Weighted Mostar indices as measures of molecular peripheral shapes with applications to graphene, graphyne and graphdiyne nanoribbons. SAR QSAR Environ. Res., 2020, 31(3), 187-208.
[http://dx.doi.org/10.1080/1062936X.2019.1708459] [PMID: 31960721]
[36]
Arockiaraj, M.; Klavžar, S.; Clement, J.; Mushtaq, S.; Balasubramanian, K.; Balasubramanian, K. Edge distance-based topological indices of strength-weighted graphs and their applications to Coronoid systems, carbon nanocones and SiO2 nanostructures. Mol. Inform., 2019, 38(11-12), 1900039.
[http://dx.doi.org/10.1002/minf.201900039] [PMID: 31529609]
[37]
Alameri, A.Q.S.; Al-Sharafi, M.S.Y. Topological indices types in Graphs and their applications; Generis Publishing: New South Wales, Australia, 2021.
[38]
Natarajan, R.; Kamalakanan, P.; Nirdosh, I. Applications of topological indices to structure-activity relationship modelling and selection of mineral collectors. Indian J. Chem., 2023, 42A, 1330-1346.
[39]
Huilgol, M.I.; Sriram, V.; Udupa, H.J.; Balasubramanian, K. Computational studies of toxicity and properties of β-diketones through topological indices and M/NM-polynomials. Comput. Theor. Chem., 2023, 1224, 114108.
[http://dx.doi.org/10.1016/j.comptc.2023.114108]
[40]
Bajaj, S.; Sambi, S.S.; Madan, A.K. Prediction of Anti-Inflammatory activity of N-Arylanthranilic acids: Computational approach using Refined Zagreb indices. Croat. Chem. Acta, 2005, 78(2), 165-174.
[41]
Huilgol, M.I.; Sriram, V.; Balasubramanian, K. Structure–activity relations for antiepileptic drugs through omega polynomials and topological indices. Mol. Phys., 2022, 120(3), e1987542.
[http://dx.doi.org/10.1080/00268976.2021.1987542]
[42]
Poojary, P.; Shenoy, G.B.; Swamy, N.N.; Ananthapadmanabha, R.; Sooryanarayana, B.; Poojary, N. Reverse Topological indices of some molecules in drugs used in the Treatment of H1N1. Biointerface Res. Appl. Chem., 2023, 13(1), 71.
[43]
Bindusree, A.R.; Cangul, N.; Lokesha, V.; Cevik, S. Zagreb polynomials of three graph operators. Filomat, 2016, 30(7), 1979-1986.
[http://dx.doi.org/10.2298/FIL1607979B]
[44]
Das, K.C.; Yurttas, A.; Togan, M.; Cevik, A.S.; Cangul, I.N. The multiplicative Zagreb indices of graph operations. J. Inequal. Appl., 2013, 2013(1), 90.
[http://dx.doi.org/10.1186/1029-242X-2013-90]
[45]
Das, K.C.; Akgunes, N.; Togan, M.; Yurttas, A.; Cangul, I.N.; Cevik, A.S. On the first Zagreb index and multiplicative Zagreb coindices of graphs. Seria Matematica, 2016, 24(1), 153-176.
[46]
Mishra, V.N.; Delen, S.; Cangul, I.N. Algebraic structure of graph operations in terms of degree sequences. Int. J. Anal. App., 2018, 16(6), 809-821.
[47]
Ranjini, P.S.; Lokesha, V.; Cangül, I.N. On the Zagreb indices of the line graphs of the subdivision graphs. Appl. Math. Comput., 2011, 218(3), 699-702.
[http://dx.doi.org/10.1016/j.amc.2011.03.125]
[48]
Togan, M.; Yurttas, A.; Cangul, I.N. Zagreb and multiplicative Zagreb indices of r-subdivision graphs of double graphs. Scientia Magna, 2017, 12(1), 115-119.
[49]
Yurtas, A.; Togan, M.; Lokesha, V.; Cangul, I.N.; Gutman, I. Inverse problem for Zagreb indices. J. Math. Chem., 2019, 57(2), 609-615.
[http://dx.doi.org/10.1007/s10910-018-0970-x]
[50]
Samiei, Z.; Movahedi, F. Investigating graph invariants for predicting properties of chemical structures of Antiviral drugs. Polycycl. Aromat. Compd., 2023, 1-18.
[http://dx.doi.org/10.1080/10406638.2023.2283625]
[51]
Ul Haq Bokhary, S.A.; Imran, M.; Akhter, S.; Manzoor, S. Molecular topological invariants of certain chemical networks. Main Group Met. Chem., 2021, 44(1), 141-149.
[http://dx.doi.org/10.1515/mgmc-2021-0010]
[52]
Imran, M.; Akhter, S.; Iqbal, Z. Edge Mostar index of chemical structures and nanostructures using graph operations. Int. J. Quantum Chem., 2020, 120(15), e26259.
[http://dx.doi.org/10.1002/qua.26259]
[53]
Gutman, I.; Tosovic, J. ovi, J. Testing the quality of molecular structure descriptors. Vertex-degree-based topological indices. J. Serb. Chem. Soc., 2013, 78(6), 805-810.
[http://dx.doi.org/10.2298/JSC121002134G]
[54]
Gutman, I. Degree-based topological indices. Croat. Chem. Acta, 2013, 86(4), 351-361.
[http://dx.doi.org/10.5562/cca2294]
[55]
Gutman, I.; Furtula, B.; Das, K.C. Extended energy and its dependence on molecular structure. Can. J. Chem., 2017, 95(5), 526-529.
[http://dx.doi.org/10.1139/cjc-2016-0636]
[56]
Hayat, S.; Wang, S.; Liu, J.B. Valency-based topological descriptors of chemical networks and their applications. Appl. Math. Model., 2018, 60, 164-178.
[http://dx.doi.org/10.1016/j.apm.2018.03.016]
[57]
Wardecki, D.; Dołowy, M.; Bober-Majnusz, K. Evaluation of the usefulness of topological indices for predicting selected physicochemical properties of bioactive substances with Anti-Androgenic and Hypouricemic activity. Molecules, 2023, 28(15), 5822.
[http://dx.doi.org/10.3390/molecules28155822] [PMID: 37570792]
[58]
Delen, S.; Naci Cangul, I. A New Graph Invariant. Turkish J. Anal. Num. Theory, 2018, 6(1), 30-33.
[http://dx.doi.org/10.12691/tjant-6-1-4]
[59]
Delen, S.; Togan, M.; Yurttas, A.; Ana, U.; Cangul, I. N. The effect of edge and vertex deletion on omega invariant. Appl. Anal. Discr. Math., 2020, 14(1)
[60]
Delen, S.; Demirci, M.; Cevik, A.S.; Cangul, I.N. On Omega index and average degree of graphs. J. Math, 2021, 2021
[http://dx.doi.org/10.1155/2021/5565146]
[61]
Delen, S.; Yurttas, A.; Togan, M.; Cangul, I.N. Omega invariant of graphs and cyclicness. Appl. Sci. (Basel), 2019, 21, 91-95.
[62]
Sanli, U.; Celik, F.; Delen, S.; Cangul, I. Connectedness criteria for graphs by means of omega invariant. Filomat, 2020, 34(2), 647-652.
[http://dx.doi.org/10.2298/FIL2002647S]
[63]
Oz, M.S.; Cangul, I.N. Bounds for matching number of fundamental realizations according to new graph invariant omega. Proc. Jangjeon Math. Soc., 2020, 23(1), 23-37.
[64]
Ozden, H.; Zihni, F.E.; Erdogan, F.O.; Cangul, I.N.; Srivastava, G.; Srivastava, H.M. Independence number of graphs and line graphs of trees by means of omega invariant. Revista de la Real Academia de Ciencias Exactas, Físicas y Naturales. Serie A, Matemáticas, 2020, 114(2)
[65]
Oz, M.S.; Cangul, I.N. A survey of the maximal and the minimal nullity in terms of omega invariant on graphs. Acta Univ. Sapientiae Matem., 2023, 15(2), 337-353.
[http://dx.doi.org/10.2478/ausm-2023-0019]
[66]
Demirci, M.; Gunes, A.; Delen, S.; Cangul, I.N. The effect of omega invariant on some topological graph indices. Creative Math. Inform., 2021, 30(2), 175-180.
[http://dx.doi.org/10.37193/CMI.2021.02.07]
[67]
Gunes, A.Y. New relations between Zagreb indices and Omega invariant. Curr. Org. Synth., 2023, 2023, 20.
[PMID: 37278040]
[68]
Gutman, I.; Togan, M.; Yurttas, A.; Cevik, A.S.; Cangul, I.N. Inverse problem for Sigma index. MATCH Commun. Math. Comput. Chem., 2018, 79(2), 491-508.
[69]
Togan, M.; Yurttas, A.; Sanli, U.; Celik, F.; Cangual, I. Inverse problem for Bell index. Filomat, 2020, 34(2), 615-621.
[http://dx.doi.org/10.2298/FIL2002615T]
[70]
Demirci, M.; Delen, S.; Cevik, A.S.; Cangul, I.N. Omega Index of Line and Total graphs. J. Math, 2021, 2021
[http://dx.doi.org/10.1155/2021/5552202]
[71]
Togan, M.; Gunes, A.Y.; Delen, S.; Cangul, I.N. Omega invariant of the Line graphs of Unicyclic graphs. Montes Taurus J. Pure Appl. Math., 2020, 2(2), 45-48.
[72]
Demirci, M.; Ozbek, A.; Akbayrak, O.; Cangul, I.N. Lucas graphs. J. Appl. Math. Comput., 2021, 65(1-2), 93-106.
[http://dx.doi.org/10.1007/s12190-020-01382-z]
[73]
Gunes, A.Y.; Delen, S.; Demirci, M.; Cevik, A.S.; Cangul, I.N. Fibonacci Graphs. Symmetry (Basel), 2020, 12(1383)
[74]
Demirci, M.; Cangul, I.N. Tribonacci graphs. ITM Web of Conf., 2020, 34(3), 01002.
[75]
Gunes, A.Y. Omega invariant of complement graphs and Nordhaus-Gaddum type results. Curr. Org. Synth., 2023, 21.
[PMID: 37859329]
[76]
Ascioglu, M.; Demirci, M.; Cangul, I.N. Omega invariant of union, join and corona product of two graphs. Advanced Studies in Contemporary Mathematics, 2020, 30(3), 297-306.
[77]
Xing, B.H.; Ozalan, N.U.; Liu, J.B. The degree sequence on tensor and cartesian products of graphs and their omega index. AIMS Math., 2023, 8(7), 16618-16632.
[http://dx.doi.org/10.3934/math.2023850]
[78]
Huilgol, M.I.; D’Souza, G.D.; Cangul, I.N. Omega invariant of some Cayley graphs; Preprint, 2024.
[79]
Huilgol, M.I.; D’Souza, G.D.; Cangul, I.N. Omega indices of some Sierpiński type graphs; Preprint, 2024.
[80]
Yurttas, A.; Togan, M.; Delen, S.; Cangul, I.N. Omega invariants and its applications in graph theory. Proc. Book MICOPAM, 2018, 2018, 7.
[81]
Li, X.; Li, Z.; Wang, L. The inverse problems for some topological indices in combinatorial chemistry. J. Comput. Biol., 2003, 10(1), 47-55.
[http://dx.doi.org/10.1089/106652703763255660] [PMID: 12676050]
[82]
Aasi, M.S.; Asif, M.; Iqbal, T.; Ibrahim, M. Radio labellings of Lexicographic product of some graphs J. Math, 2021, 2021
[83]
Zhang, X.; Fang, Z. The Spectrum of weighted lexicographic production self-complementary graphs. IEEE Access, 2023, 11, 85374-85383.
[http://dx.doi.org/10.1109/ACCESS.2023.3303895]
[84]
Akhter, S.; Imran, M. On degree-based topological descriptors of strong product graphs. Can. J. Chem., 2016, 94(6), 559-565.
[http://dx.doi.org/10.1139/cjc-2015-0562]
[85]
Delen, S.; Cangul, I.N. Extremal Problems on Components and Loops in Graphs. Acta Math. Sin., 2019, 35(2), 161-171.
[http://dx.doi.org/10.1007/s10114-018-8086-6]

Rights & Permissions Print Cite
Article Metrics
9
1
Wayfinder Image
TIMBC 2025
© 2025 Bentham Science Publishers | Privacy Policy