The geodesic-transversal problem on graphs of diameter at most three

Articles in Press

Document Type : Original paper

Authors

1 Department of Mathematics, Malankara Catholic College, Manonmaniam Sundaranar University, Tirunelveli 627012, Tamil Nadu, India

2 Department of Mathematics, Malankara Catholic College, Mariagiri, Kaliyakkavilai, Tamil Nadu-629153, India

Abstract

In graph theory, finding the minimal set of vertices with specific covering properties is important. A geodesic transversal of a graph $G$ is a set $S$ of vertices such that every maximal geodesic of $G$ includes at least one vertex from S. The minimum size of a geodesic transversal of $G$ is called geodesic transversal number, denoted as $gt(G)$. It helps in understanding how graphs navigate, how efficiently they communicate, and how to monitor networks. This work finds $gt(G)$ for all graphs with a diameter of 2 and expands the analysis to various classes of graphs with a diameter of 3.

Keywords

Main Subjects

References

1] A.M. Anto, R. Rajeshkumar, L.E. Preshiba, and V.M.M. Rose, Insights into IF-geodetic convexity in intuitionistic fuzzy graphs: Harnessing the IF-geodetic wiener index for global human trading analysis and IF-geodetic cover for gateway
node identification, Symmetry 17 (2025), no. 8, 1277. https://doi.org/10.3390/sym17081277
[2] A. Bendali-Braham, N. Ikhlef-Eschouf, and M. Blidia, Some results on the bchromatic number in complementary prism graphs, RAIRO Oper. Res. 53 (2019), no. 4, 1187–1195. https://doi.org/10.1051/ro/2018054
[3] A.A. Bertossi, Dominating sets for split and bipartite graphs, Inform. Process. Lett. 19 (1984), no. 1, 37–40. https://doi.org/10.1016/0020-0190(84)90126-1
[4] B. Brešar, T. Kos, R. Krivoš-Belluš, and G. Semanišin, Hitting subgraphs in $P_4$-tidy graphs, Appl. Math. Comput. 352 (2019), 211–219. https://doi.org/10.1016/j.amc.2019.01.074
[5] D.M. Cardoso, P. Carvalho, M.A.A. de Freitas, and C.T. Vinagre, Spectra, signless Laplacian and Laplacian spectra of complementary prisms of graphs, Linear Algebra Appl. 544 (2018), 325–338. https://doi.org/10.1016/j.laa.2018.01.020
[6] U. Chandran S V, G. Di Stefano, E.J. Thomas, and J. Tuite, Colouring a graph with position sets, Ars Math. Contemp. (2025), In–press.
[7] M.A. Duarte, L. Penso, D. Rautenbach, and U. dos Santos Souza, Complexity properties of complementary prisms, J. Comb. Optim. 33 (2017), no. 2, 365–372. https://doi.org/10.1007/s10878-015-9968-5
8] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, San Francisco, 1979.
[9] M.R. Garey and R.E. Tarjan, A linear-time algorithm for finding all feedback vertices, Inform. Process. Lett. 7 (1978), no. 6, 274–276. https://doi.org/10.1016/0020-0190(78)90015-7
[10] F. Harary and R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976), 191–195.
[11] T. Haynes, M. Henning, P. Slater, and L. Merwe, The complementary product of two graphs, Bull. Inst. Combin. Appl. 51 (2007), 21–30.
[12] T.W. Haynes, M.A. Henning, and L.C. Van Der Merwe, Domination and total domination in complementary prisms, J. Comb. Optim. 18 (2009), no. 1, 23–37. https://doi.org/10.1007/s10878-007-9135-8
[13] T. James, S. Klavžar, and A. Vijayakumar, The domination game on split graphs, Bull. Aust. Math. Soc. 99 (2019), no. 2, 327–337. https://doi.org/10.1017/S0004972718001053
[14] D. Korže and A. Vesel, General position sets in two families of cartesian product graphs, Mediterr. J. Math. 20 (2023), no. 4, 203. https://doi.org/10.1007/s00009-023-02416-z
[15] P. Manuel, B. Brešar, and S. Klavžar, The geodesic-transversal problem, Appl. Math. Comput. 413 (2022), 126621.
https://doi.org/10.1016/j.amc.2021.126621
[16] P. Manuel, B. Brešar, and S. Klavžar, Geodesic packing in graphs, Appl. Math. Comput. 459 (2023), 128277. https://doi.org/10.1016/j.amc.2023.128277
[17] P. Manuel, B. Brešar, and S. Klavžar, The geodesic transversal problem on some networks, Comp. Appl. Math. 42 (2023), no. 1, 59. https://doi.org/10.1007/s40314-023-02199-9
[18] P. Manuel and S. Klavžar, A general position problem in graph theory, Bulletin of the Australian Mathematical Society 98 (2018), no. 2, 177–187. https://doi.org/10.1017/S0004972718000473
19] D. Meierling, Rautenbach D. Protti, F., and A.R. de Almeida, Cycles in complementary prisms, Discrete Appl. Math. 193 (2015), 180–186. https://doi.org/10.1016/j.dam.2015.04.016
[20] R.E. Miller and J.W. Thatcher (eds.), Complexity of computer computations, The IBM Research Symposia Series, Yorktown Heights, N.Y., Plenum Press, 1972.
[21] P.K. Neethu and U. Chandran S V, A note on the convexity number of the complementary prisms of trees, Discrete Appl. Math. 319 (2022), 480–486. https://doi.org/10.1016/j.dam.2021.07.033
[22] P.K. Neethu, U. Chandran S V, M. Changat, and S. Klavˇzar, On the general position number of complementary prisms, Fund. Inform. 178 (2021), no. 3, 267–281. https://doi.org/10.3233/FI-2021-2006
[23] P.K. Neethu, U. Chandran S V, and J.R. Nascimento, On the monophonic convexity in complementary prisms, Discrete Appl. Math. 343 (2024), 224–230. https://doi.org/10.1016/j.dam.2023.10.024
[24] I. Peterin and G. Semanišin, Geodesic transversal problem for join and lexicographic product of graphs, Comp. Appl. Math. 41 (2022), no. 4, 128. https://doi.org/10.1007/s40314-022-01834-1
[25] I. Peterin and S. Semanišin, On maximal shortest paths cover, Mathematics 9 (2021), no. 14, 1592.
https://doi.org/10.3390/math9141592
[26] R. Rajeshkumar and A.M. Anto, Fuzzy detour convexity and fuzzy detour covering in fuzzy graphs, Turkish Journal of Computer and Mathematics Education 12 (2021), no. 2, 2170–2175. https://doi.org/10.17762/turcomat.v12i2.1898
[27] , Some domination parameters in intuitionistic fuzzy graphs, American Institute of Physics Conference Series, vol. 2516, 2022, p. 200016. https://doi.org/10.1063/5.0108668
[28] R. Rajeshkumar, A.M. Anto, and V.M.M. Rose, Fuzzy geodetic and detour spectra: Geodetic-Laplacian energy in fuzzy graphs, Eur. J. Pure Appl. Math. 18 (2025), no. 4, 6307. https://doi.org/10.29020/nybg.ejpam.v18i4.6307
[29] S. Rout, P.K. Mishra, and G.K. Das, Total Roman domination and total domination in unit disk graphs, Commun. Comb. Optim. 10 (2025), no. 4, 803–823. https://doi.org/10.22049/cco.2024.28647.1650
[30] D. Roy, S. Klavˇzar, and A. Lakshmanan, Mutual-visibility and general position in double graphs and in Mycielskians, Appl. Math. Comput. 488 (2025), 129131. https://doi.org/10.1016/j.amc.2024.129131
[31] P.J. Slater, Leaves of trees, Congressus Numerantium 14 (1975), 549–559.
[32] E.J. Thomas, U. Chandran S V, J. Tuite, and G. Di Stefano, On monophonic position sets in graphs, Discrete Appli. Math. 354 (2024), 72–82. https://doi.org/10.1016/j.dam.2023.02.021
[33] E.J. Thomas, U. Chandran S V, J. Tuite, and G. Di Stefano, On the general position number of Mycielskian graphs, Discrete Appl. Math. 353 (2024), 29–43. https://doi.org/10.1016/j.dam.2024.03.015
[34] J. Tian and S. Klavžar, Variety of general position problems in graphs, Bull. Malays. Math. Sci. Soc. 48 (2025), no. 1, 5.
https://doi.org/10.1007/s40840-024-01788-z
[35] J. Tian and K. Xu, The general position number of cartesian products involving a factor with small diameter, Appl. Math. Comput. 403 (2021), 126206. https://doi.org/10.1016/j.amc.2021.126206
[36] J. Tian, K. Xu, and S. Klavžar, The general position number of the cartesian product of two trees, Bull. Aust. Math. Soc. 104 (2021), no. 1, 1–10. https://doi.org/10.1017/S0004972720001276
[37] J. Tuite, E.J. Thomas, and U. Chandran S V, On some extremal position problems for graphs, Ars Math. Contemp. 25 (2025), no. 1, #P1.09. https://doi.org/10.26493/1855-3974.3094.bc6
[38] E.K. Welton, S. Khudairi, and J. Tuite, Lower general position in cartesian products, Commun. Comb. Optim. 10 (2025), no. 1, 110–125. https://doi.org/10.22049/cco.2024.29171.1879
[39] L.M. Zatesko, R. Carmo, A.L. Guedes, A. Zorzi, R.C. Machado, and C.M. Figueiredo, On the chromatic index of complementary prisms, Acta Math. Univ. Comenian. 88 (2019), no. 3, 1071–1077.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 13 June 2026

Files

Share

How to cite

Statistics