On strong geodeticity in the lexicographic product of graphs

S. Gajavalli; A. Berin Greeni; S. Gajavalli; A. Berin Greeni

doi:10.3934/math.2024991

AIMS Mathematics

2024, Volume 9, Issue 8: 20367-20389. doi: 10.3934/math.2024991

Previous Article Next Article

Research article

On strong geodeticity in the lexicographic product of graphs

S. Gajavalli ,
A. Berin Greeni ^,

School of Advanced Sciences, Vellore Institute of Technology, Chennai, India

Received: 21 February 2024 Revised: 10 May 2024 Accepted: 14 May 2024 Published: 24 June 2024
MSC : 05C12

The strong geodetic number of a graph and its edge counterpart are recent variations of the pioneering geodetic number problem. Covering every vertex and edge of $ G $, respectively, using a minimum number of vertices and the geodesics connecting them, while ensuring that one geodesic is fixed between each pair of these vertices, is the objective of the strong geodetic number problem and its edge version. This paper investigates the strong geodetic number of the lexicographic product involving graph classes that include complete graph $ K_{m} $, path $ P_{m} $, cycle $ C_{m} $ and star $ K_{1, \, m} $ paired with $ P_{n} $ and with $ C_{n} $. Furthermore, the parameter is studied in the lexicographic product of, arbitrary trees with diameter-2 graphs whose geodetic number is equal to 2, $ K_{n}-e $ with $ K_{2} $ and their converses. Upper and lower bounds for the parameter are established for the lexicographic product of general graphs and in addition, the edge variant of the aforementioned problem is studied in certain lexicographic products. The strong geodetic parameters considered in this paper have pivotal applications in social network problems, thereby making them indispensable in the realm of graph theoretical research. This work contributes to the expansion of the current state of research pertaining to strong geodetic parameters in product graphs.
- strong geodetic number,
- lexicographic product,
- strong edge geodetic number,
- shortest path
Citation: S. Gajavalli, A. Berin Greeni. On strong geodeticity in the lexicographic product of graphs[J]. AIMS Mathematics, 2024, 9(8): 20367-20389. doi: 10.3934/math.2024991

Related Papers:

Abstract

The strong geodetic number of a graph and its edge counterpart are recent variations of the pioneering geodetic number problem. Covering every vertex and edge of $ G $, respectively, using a minimum number of vertices and the geodesics connecting them, while ensuring that one geodesic is fixed between each pair of these vertices, is the objective of the strong geodetic number problem and its edge version. This paper investigates the strong geodetic number of the lexicographic product involving graph classes that include complete graph $ K_{m} $, path $ P_{m} $, cycle $ C_{m} $ and star $ K_{1, \, m} $ paired with $ P_{n} $ and with $ C_{n} $. Furthermore, the parameter is studied in the lexicographic product of, arbitrary trees with diameter-2 graphs whose geodetic number is equal to 2, $ K_{n}-e $ with $ K_{2} $ and their converses. Upper and lower bounds for the parameter are established for the lexicographic product of general graphs and in addition, the edge variant of the aforementioned problem is studied in certain lexicographic products. The strong geodetic parameters considered in this paper have pivotal applications in social network problems, thereby making them indispensable in the realm of graph theoretical research. This work contributes to the expansion of the current state of research pertaining to strong geodetic parameters in product graphs.

References

[1]	P. Manuel, B. Bresar, S. Klavzar, The geodesic-transversal problem, Appl. Math. Comput., 413 (2022), 126621. https://doi.org/10.1016/j.amc.2021.126621 doi: 10.1016/j.amc.2021.126621
[2]	F. Foucaud, S. S. Kao, R. Klasing, M. Miller, J. Ryan, Monitoring the edges of a graph using distances, Discrete Appl. Math., 319 (2022), 424–438. https://doi.org/10.1016/j.dam.2021.07.002 doi: 10.1016/j.dam.2021.07.002
[3]	P. Manuel, B. Bresar, S. Klavzar, Geodesic packing in graphs, Appl. Math. Comput., 459 (2023), 128277. https://doi.org/10.1016/j.amc.2023.128277 doi: 10.1016/j.amc.2023.128277
[4]	Y. L. Shang, Lack of Gromov-hyperbolicity in small-world networks, Open Math., 10 (2012), 1152–1158. https://doi.org/10.2478/s11533-012-0032-8 doi: 10.2478/s11533-012-0032-8
[5]	Y. L. Shang, Non-hyperbolicity of random graphs with given expected degrees, Stoch. Models, 29 (2013), 451–462. https://doi.org/10.1080/15326349.2013.838510 doi: 10.1080/15326349.2013.838510
[6]	J. B. Liu, X. Zhang, J. D. Cao, L. P. Chen, Mean first-passage time and robustness of complex cellular mobile communication network, IEEE T. Netw. Sci. Eng., 11 (2024), 3066–3076. https://doi.org/10.1109/TNSE.2024.3358369 doi: 10.1109/TNSE.2024.3358369
[7]	J. B. Liu, Y. Bao, W. T. Zheng, Analyses of some structural properties on a class of hierarchical scale-free networks, Fractals, 30 (2022), 2250136. https://doi.org/10.1142/S0218348X22501365 doi: 10.1142/S0218348X22501365
[8]	Z. Z. Zhang, S. G. Zhou, L. C. Chen, M. Yin, J. H. Guan, The exact solution of the mean geodesic distance for Vicsek fractals, J. Phys. A: Math. Theor., 41 (2008), 485102. https://doi.org/10.1088/1751-8113/41/48/485102 doi: 10.1088/1751-8113/41/48/485102
[9]	F. Harary, E. Loukakis, C. Tsouros, The geodetic number of a graph, Math. Comput. Model., 17 (1993), 89–95. https://doi.org/10.1016/0895-7177(93)90259-2 doi: 10.1016/0895-7177(93)90259-2
[10]	I. M. Pelayo, Geodesic convexity in graphs, 1 Eds., New York: Springer, 2013. https://doi.org/10.1007/978-1-4614-8699-2
[11]	M. Atici, Computational complexity of geodetic set, Int. J. Comput. Math., 79 (2002), 587–591. https://doi.org/10.1080/00207160210954 doi: 10.1080/00207160210954
[12]	M. C. Dourado, F. Protti, D. Rautenbach, J. L. Szwarcfiter, Some remarks on the geodetic number of a graph, Discrete Math., 310 (2010), 832–837. https://doi.org/10.1016/j.disc.2009.09.018 doi: 10.1016/j.disc.2009.09.018
[13]	M. Bedo, J. V. Leite, R. A. Oliveira, F. Protti, Geodetic convexity and kneser graphs, Appl. Math. Comput., 449 (2023), 127964. https://doi.org/10.1016/j.amc.2023.127964 doi: 10.1016/j.amc.2023.127964
[14]	S. Gajavalli, A. B. Greeni, On geodesic convexity in Mycielskian of graphs, J. Adv. Comput. Intell. Intell. Inform., 27 (2023), 119–123. https://doi.org/10.20965/jaciii.2023.p0119 doi: 10.20965/jaciii.2023.p0119
[15]	D. Castonguay, E. M. Coelho, H. Coelho, J. R. Nascimento, On the geodetic number of complementary prisms, Inform. Process. Lett., 144 (2019), 39–42. https://doi.org/10.1016/j.ipl.2018.12.007 doi: 10.1016/j.ipl.2018.12.007
[16]	A. B. Greeni, S. Gajavalli, Geodetic parameters in tree derived architectures, TWMS J. App. and Eng. Math., 14 (2024), 730–737.
[17]	D. Chakraborty, H. Gahlawat, B. Roy, Algorithms and complexity for geodetic sets on partial grids, Theor. Comput. Sci., 979 (2023), 114217. https://doi.org/10.1016/j.tcs.2023.114217 doi: 10.1016/j.tcs.2023.114217
[18]	M. Atici, On the edge geodetic number of a graph, Int. J. Comput. Math., 80 (2003), 853–861. https://doi.org/10.1080/0020716031000103376 doi: 10.1080/0020716031000103376
[19]	A. Hansberg, L. Volkmann, On the geodetic and geodetic domination numbers of a graph, Discrete Math., 310 (2010), 2140–2146. https://doi.org/10.1016/j.disc.2010.04.013 doi: 10.1016/j.disc.2010.04.013
[20]	H. Abdollahzadeh Ahangar, V. Samodivkin, S. M. Sheikholeslami, A. Khodkar, The restrained geodetic number of a graph, Bull. Malays. Math. Sci. Soc., 38 (2015), 1143–1155. https://doi.org/10.1007/s40840-014-0068-y doi: 10.1007/s40840-014-0068-y
[21]	P. Manuel, S. Klavzar, A. Xavier, A. Arokiaraj, E. Thomas, Strong geodetic problem in networks, Discuss. Math. Graph T., 40 (2020), 307–321. http://doi.org/10.7151/dmgt.2139 doi: 10.7151/dmgt.2139
[22]	P. Manuel, S. Klavzar, A. Xavier, A. Arokiaraj, E. Thomas, Strong edge geodetic problem in networks, Open Math., 15 (2017), 1225–1235. https://doi.org/10.1515/math-2017-0101 doi: 10.1515/math-2017-0101
[23]	S. Klavzar, P. Manuel, Strong geodetic problem in grid-like architectures, Bull. Malays. Math. Sci. Soc., 41 (2018), 1671–1680. https://doi.org/10.1007/s40840-018-0609-x doi: 10.1007/s40840-018-0609-x
[24]	V. Gledel, V. Irsic, Strong geodetic number of complete bipartite graphs, crown graphs and hypercubes, Bull. Malays. Math. Sci. Soc., 43 (2020), 2757–2767. https://doi.org/10.1007/s40840-019-00833-6 doi: 10.1007/s40840-019-00833-6
[25]	V. Irsic, M. Konvalinka, Strong geodetic problem on complete multipartite graphs, Ars Math. Contemp., 17 (2019), 481–491. http://doi.org/10.26493/1855-3974.1725.2e5 doi: 10.26493/1855-3974.1725.2e5
[26]	V. Irsic, S. Klavzar, Strong geodetic problem on Cartesian products of graphs, RAIRO-Oper. Res., 52 (2018), 205–216. https://doi.org/10.1051/ro/2018003 doi: 10.1051/ro/2018003
[27]	E. Zmazek, Strong edge geodetic problem on grids, Bull. Malays. Math. Sci. Soc., 44 (2021), 3705–3724. https://doi.org/10.1007/s40840-021-01137-4 doi: 10.1007/s40840-021-01137-4
[28]	A. Xavier, D. Mathew, S. Theresal, E. S. Varghese, Some results on strong edge geodetic problem in graphs, Commun. Math. Appl., 11 (2020), 403–413. https://doi.org/10.26713/cma.v11i3.1385 doi: 10.26713/cma.v11i3.1385
[29]	S. Klavžar, E. Zmazek, Strong edge geodetic problem on complete multipartite graphs and some extremal graphs for the problem, Bull. Iran. Math. Soc., 50 (2024), 13. https://doi.org/10.1007/s41980-023-00849-6 doi: 10.1007/s41980-023-00849-6
[30]	R. Hammack, W. Imrich, S. Klavzar, Handbook of product graphs, 2 Eds., New York: CRC Press, 2011. https://doi.org/10.1201/b10959
[31]	F. Li, W. Wang, Z. B. Xu, H. X. Zhao, Some results on the lexicographic product of vertex-transitive graphs, Appl. Math. Lett., 24 (2011), 1924–1926. https://doi.org/10.1016/j.aml.2011.05.021 doi: 10.1016/j.aml.2011.05.021
[32]	F. Harary, G. W. Wilcox, Boolean operations on graphs, Math. Scand., 20 (1967), 41–51.
[33]	W. H. Ma, G. H. Dong, Y. Y. Lu, N. Wang, Lexicographic product graphs $P_{m}[P_{n}]$ are antimagic, AKCE Int. J. Graphs Co., 15 (2018), 271–283. http://doi.org/10.1016/j.akcej.2017.10.005 doi: 10.1016/j.akcej.2017.10.005
[34]	I. Peterin, G. Semanisin, Geodesic transversal problem for join and lexicographic product of graphs, Comp. Appl. Math., 41 (2022), 128. https://doi.org/10.1007/s40314-022-01834-1 doi: 10.1007/s40314-022-01834-1
[35]	D. Kuziak, J. A. Rodríguez-Velázquez, Total mutual-visibility in graphs with emphasis on lexicographic and Cartesian products, Bull. Malays. Math. Sci. Soc., 46 (2023), 197. https://doi.org/10.1007/s40840-023-01590-3 doi: 10.1007/s40840-023-01590-3
[36]	Y. X. Li, S. A. Xu, H. B. Hua, X. F. Pan, On the resistance diameter of the Cartesian and lexicographic product of paths, J. Appl. Math. Comput., 68 (2022), 1743–1755. https://doi.org/10.1007/s12190-021-01587-w doi: 10.1007/s12190-021-01587-w
[37]	A. Gispert-Fernández, J. A. Rodrıguez-Velázquez, The equidistant dimension of graphs: NP-completeness and the case of lexicographic product graphs, AIMS Mathematics, 9 (2024), 15325–15345. http://doi.org/10.3934/math.2024744 doi: 10.3934/math.2024744
[38]	H. A. Ganie, A. Ingole, U. Deshmukh, Y. L. Shang, On the skew characteristics polynomial/eigenvalues of operations on bipartite oriented graphs and applications, Res. Math., 11 (2024), 2313343. https://doi.org/10.1080/27684830.2024.2313343 doi: 10.1080/27684830.2024.2313343
[39]	A. Alhevaz, M. Baghipur, H. A. Ganie, Y. L. Shang, The generalized distance spectrum of the join of graphs, Symmetry, 12 (2020), 169. https://doi.org/10.3390/sym12010169 doi: 10.3390/sym12010169
[40]	W. Carballosa, A. de la Cruz, J. M. Rodríguez, Gromov hyperbolicity in lexicographic product graphs, Proc. Math. Sci., 129 (2019), 5. https://doi.org/10.1007/s12044-018-0451-y doi: 10.1007/s12044-018-0451-y
[41]	B. Bresar, T. K. Sumenjak, A. Tepeh, The geodetic number of the lexicographic product of graphs, Discrete Math., 311 (2011), 1693–1698. https://doi.org/10.1016/j.disc.2011.04.004 doi: 10.1016/j.disc.2011.04.004
[42]	V. Gledel, V. Irsic, S. Klavzar, Strong geodetic cores and Cartesian product graphs, Appl. Math. Comput., 363 (2019), 124609. https://doi.org/10.1016/j.amc.2019.124609 doi: 10.1016/j.amc.2019.124609
[43]	Z. Wang, Y. P. Mao, H. F. Ge, C. Magnant, Strong geodetic number of graphs and connectivity, Bull. Malays. Math. Sci. Soc., 43 (2020), 2443–2453. https://doi.org/10.1007/s40840-019-00809-6 doi: 10.1007/s40840-019-00809-6
[44]	F. Buckley, F. Harary, Distance in graphs, New York: Addison-Wesley Publishing Company, 1990.
[45]	G. Chartrand, P. Zhang, Extreme geodesic graphs, Czech. Math. J., 52 (2002), 771–780. https://doi.org/10.1023/B:CMAJ.0000027232.97642.45 doi: 10.1023/B:CMAJ.0000027232.97642.45

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)