Lower General Position in Cartesian Products

Document Type : Original paper

Authors

1 School of Mathematics and Statistics, Open University, Milton Keynes, UK

2 School of Mathematics, University of Cardiff, UK

Abstract

A subset $S$ of vertices of a graph $G$ is in general position if no shortest path in $G$ contains three vertices of $S$. The general position problem consists of finding the number of vertices in a largest general position set of $G$, whilst the lower general position problem asks for a smallest maximal general position set. In this paper we determine the lower general position numbers of several families of Cartesian products. We also show that the existence of small maximal general position sets in a Cartesian product is connected to a special type of general position set in the factors, which we call a terminal set, for which adding any vertex $u$ from outside the set creates three vertices in a line with $u$ as an endpoint. We give a constructive proof of the existence of terminal sets for graphs with diameter at most three. We also present conjectures on the existence of terminal sets for all graphs and a lower bound on the lower general position number of a Cartesian product in terms of the lower general position numbers of its factors.

Keywords

Main Subjects

References

[1] B.S. Anand, U. Chandran S.V., M. Changat, S. Klavžar, and E.J. Thomas, Characterization of general position sets and its applications to cographs and bipartite graphs, Appl. Math. Comput. 359 (2019), 84–89.  https://doi.org/10.1016/j.amc.2019.04.064
[2] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, American Elsevier Publishing Company, North-Holland, 1976.
[3] U. Chandran S.V. and G.J. Parthasarathy, The geodesic irredundant sets in graphs, Int. J. Math. Combin. 4 (2016), 135–143.
[4] X. Chen and V. Chvátal, Problems related to a de bruijn–erd¨os theorem, Discrete Appl. Math. 156 (2008), no. 11, 2101–2108.  https://doi.org/10.1016/j.dam.2007.05.036
[5] S. Cicerone, G. Di Stefano, and S. Klavžar, On the mutual visibility in cartesian products and triangle-free graphs, Appl. Math. Comput. 438 (2023), Article ID: 127619.  https://doi.org/10.1016/j.amc.2022.127619
[6] G. Di Stefano, Mutual visibility in graphs, Appl. Math. Comput. 419 (2022), Article ID: 126850. https://doi.org/10.1016/j.amc.2021.126850
[7] G. Di Stefano, S. Klavžar, A. Krishnakumar, J. Tuite, and I. Yero, Lower general position sets in graphs, Discuss. Math. Graph Theory (2023), In press.
[8] H.E. Dudeney, Amusements in Mathematics, Nelson, Edinburgh, 1917.
[9] G. Erskine, personal communication, (2023).
[10] M. Gardner, Mathematical games: combinatorial problems, some old, some new and all newly attacked by computer, Sci. Amer 235 (1976), no. 4, 131–137.
[11] M. Ghorbani, H.R. Maimani, M. Momeni, F. Rahimi Mahid, S. Klavžar, and G. Rus, The general position problem on kneser graphs and on some graph operations, Discuss. Math. Graph Theory 41 (2021), no. 4, 1199–1213. https://doi.org/10.7151/dmgt.2269
[12] W. Imrich, S. Klavžar, and D.F. Rall, Topics in Graph Theory. Graphs and their Cartesian Product, CRC Press, 2008.
[13] S. Klavžar, B. Patkós, G. Rus, and I.G. Yero, On general position sets in Cartesian products, Results Math. 76 (2021), no. 3, Article ID: 123.  https://doi.org/10.1007/s00025-021-01438-x
[14] D. Korže and A. Vesel, General position sets in two families of Cartesian product graphs, Mediterr. J. Math. 20 (2023), no. 4, Article ID: 203.  https://doi.org/10.1007/s00009-023-02416-z
[15] D. Korže and A. Vesel, Mutual-visibility sets in cartesian products of paths and cycles, Results Math. 79 (2024), no. 3, Article ID: 116.  https://doi.org/10.1007/s00025-024-02139-x
[16] P. Manuel and S. Klavžar, A general position problem in graph theory, Bull. Aust. Math. Soc. 98 (2018), no. 2, 177–187. https://doi.org/10.1017/S0004972718000473
[17] P. Manuel, R. Prabha, and S. Klavžar, The edge general position problem, Bull. Malays. Math. Sci. Soc. 45 (2022), no. 6, 2997–3009.  https://doi.org/10.1007/s40840-022-01319-8
[18] P.K. Neethu, S.V. Ullas Chandran, and J. Tuite, On monophonic position sets in cartesian products, preprint.
[19] J.A. RodrÍguez-Velázquez, Universal lines in graphs, Quaest. Math. 45 (2022), no. 10, 1485–1500.  https://doi.org/10.2989/16073606.2021.1950862
[20] E.J. Thomas, U. Chandran S.V., J. Tuite, and G. Di Stefano, On monophonic position sets in graphs, Discrete Appl. Math. (2023), In press.  https://doi.org/10.1016/j.dam.2023.02.021
[21] J. Tian and K. Xu, The general position number of cartesian products involving a factor with small diameter, Appl. Math. Comput. 403 (2021), Article ID: 126206.  https://doi.org/10.1016/j.amc.2021.126206
[22] 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
 
Communications in Combinatorics and Optimization
Volume 10, Issue 1
March 2025
Pages 110-125

Files

Share

How to cite

Statistics