DMGT

A subset $S$ of vertices of a graph $G$ is a general position set if no shortest path in $G$ contains three or more vertices of $S$. In this paper, we generalise a problem of M. Gardner to graph theory by introducing the lower general position number gp$^-(G)$ of $G$, which is the number of vertices in a smallest maximal general position set of $G$. We show that $\textrm{gp}^-(G) = 2$ if and only if $G$ contains a universal line and determine this number for several classes of graphs, including Kneser graphs $K(n,2)$, line graphs of complete graphs, and Cartesian and direct products of two complete graphs. We also prove several realisation results involving the lower general position number, the general position number and the geodetic number, and compare it with the lower version of the monophonic position number. We provide a sharp upper bound on the size of graphs with given lower general position number. Finally we demonstrate that the decision version of the lower general position problem is NP-complete.

Keywords:

general position number, geodetic number, universal line, computational complexity, Kneser graphs, line graphs

References:

P. Aboulker, L. Beaudou, M. Matamala and J. Zamora, Graphs with no induced house nor induced hole have the de Bruijn-Erdős property, J. Graph Theory 100 (2022) 638–652.
https://doi.org/10.1002/jgt.22799
P. Aboulker, M. Matamala, P. Rochet and J. Zamora, A new class of graphs that satisfies the Chen-Chvátal conjecture, J. Graph Theory 87 (2018) 77–88.
https://doi.org/10.1002/jgt.22142
M.A. Adena, D.A. Holton and P.A. Kelly, Some thoughts on the no-three-in-line problem, in: Combinatorial Mathematics, D. Holton (Ed(s)), Lecture Notes in Math. 403, (Springer, Berlin, Heidelberg, 1974) 6–17..
https://doi.org/10.1007/BFb0057371
O. Aichholzer, D. Eppstein and E.M. Hainzl, Geometric dominating sets-a minimum version of the No-Three-In-Line Problem, Comput. Geom. 108 (2023) 101913.
https://doi.org/10.1016/j.comgeo.2022.101913
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
L. Beaudou, A. Bondy, X. Chen, E. Chiniforooshan, M. Chudnovsky, V. Chvátal, N. Fraiman and Y. Zwols, A De Bruijn-Erdős theorem for chordal graphs, Electron. J. Combin. 22 (2015) P1.70.
https://doi.org/10.37236/3527
P. Brass, W. Moser and J. Pach, Packing lattice points in subspaces, in: Research Problems in Discrete Geometry, (Springer, New York 2005) 417–421.
https://doi.org/10.1007/0-387-29929-7
U. Chandran S.V., M.C. Dourado and M.G.S. Thankachy, Computational and structural aspects of the geodetic and the hull numbers of shadow graphs, Discrete Appl. Math. 307 (2022) 50–61.
https://doi.org/10.1016/j.dam.2021.10.005
U. Chandran S.V and G.J. Parthasarathy, The geodesic irredundant sets in graphs, Int. J. Math. Combin. 4 (2016) 135–143.
U. Chandran S.V., S. Klavžar, P.K. Neethu and R. Sampaio, The general position avoidance game and hardness of general position games, Theoret. Comput. Sci. 988 (2024) 114370.
https://doi.org/10.1016/j.tcs.2023.114370
G. Chartrand and P. Zhang, Extreme geodesic graphs, Czechoslovak Math. J. 52 (2002) 771–780.
https://doi.org/10.1023/B:CMAJ.0000027232.97642.45
X. Chen and V. Chvátal, Problems related to a de Bruijn-Erdős theorem, Discrete Appl. Math. 156 (2008) 2101–2108.
https://doi.org/10.1016/j.dam.2007.05.036
V. Chvátal, A de Bruijn-Erdős theorem in graphs$?$, in: Graph Theory, Favorite Conjectures and Open Problems–2, R. Gera, T.W. Haynes and S.T. Hedetniemi (Ed(s)), Probl. Books in Math., (Springer, Cham, 2018) 149–176..
https://doi.org/10.1007/978-3-319-97686-0_13
A.S. Cooper, O. Pikhurko, J.R. Schmitt, G.S. Warrington, Martin Gardner's minimum no-$3$-in-a-line problem, Amer. Math. Monthly 121 (2014) 213–221.
https://doi.org/10.4169/amer.math.monthly.121.03.213
G. Di Stefano, Mutual visibility in graphs, Appl. Math. Comput. 419 (2022) 126850.
https://doi.org/10.1016/j.amc.2021.126850
H.E. Dudeney, Amusements in Mathematics (Nelson, Edinburgh, 1917).
M. Gardner, Mathematical games: combinatorial problems, some old, some new and all newly attacked by computer, Sci. Amer. 235 (1976) 131–137.
M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman and Co., 1979).
M. Ghorbani, H.R. Maimani, M. Momeni, F.R. Mahid, S. Klavžar, G. Rus, The general position problem on Kneser graphs and on some graph operations, Discuss. Math. Graph Theory 41 (2021) 1199–1213.
https://doi.org/10.7151/dmgt.2269
R.K. Guy and P.A. Kelly, The no-three-in-line problem, Canad. Math. Bull. 11 (1968) 527–531.
https://doi.org/10.4153/CMB-1968-062-3
R.R. Hall, T.H. Jackson, A. Sudbery and K. Wild, Some advances in the no-three-in-line problem, J. Combin. Theory Ser. A 18 (1975) 336–341.
https://doi.org/10.1016/0097-3165(75)90043-6
W. Imrich, S. Klavžar and D.F. Rall, Topics in Graph Theory, Graphs and their Cartesian Product (A K Peters/CRC Press, 2008).
https://doi.org/10.1201/b10613
S. Klavžar, A. Krishnakumar, J. Tuite and I.G. Yero, Traversing a graph in general position, Bull. Aust. Math. Soc. 108 (2023) 353–365.
https://doi.org/10.1017/S0004972723000102
S. Klavžar, D. Kuziak, I. Peterin and I.G. Yero, A Steiner general position problem in graph theory, Comput. Appl. Math. 40 (2021) 223.
https://doi.org/10.1007/s40314-021-01619-y
S. Klavžar, P.K. Neethu and U. Chandran S.V., The general position achievement game played on graphs, Discrete Appl. Math. 317 (2022) 109–116.
https://doi.org/10.1016/j.dam.2022.04.019
S. Klavžar, D.F. Rall and I.G. Yero, General $d$-position sets, Ars Math. Contemp. 21 (2021) #P1.03.
https://doi.org/10.26493/1855-3974.2384.77d
S. Klavžar and I.G. Yero, The general position problem and strong resolving graphs, Open Math. 17 (2019) 1126–1135.
https://doi.org/10.1515/math-2019-0088
J. Körner, On the extremal combinatorics of the Hamming space, J. Combin. Theory Ser. A 71 (1995) 112–126.
https://doi.org/10.1016/0097-3165(95)90019-5
P. Manuel and S. Klavžar, A general position problem in graph theory, Bull. Aust. Math. Soc. 98 (2018) 177–187.
https://doi.org/10.1017/S0004972718000473
P. Manuel, R. Prabha and S. Klavžar, The edge general position problem, Bull. Malays. Math. Sci. Soc. 45 (2022) 2997–3009.
https://doi.org/10.1007/s40840-022-01319-8
P.K. Neethu, U. Chandran S.V., M. Changat and S. Klavžar, On the general position number of complementary prisms, Fund. Inform. 178 (2021) 267–281.
https://doi.org/10.3233/FI-2021-2006
B. Patkós, On the general position problem on Kneser graphs, Ars Math. Contemp. 18 (2020) 273–280.
https://doi.org/10.26493/1855-3974.1957.a0f
E. Pegg Jr., Math Games. Chessboard Tasks (accessed on February 18, 2023).
https://www.mathpuzzle.com
J.A. Rodríguez-Velázquez, Universal lines in graphs, Quaest. Math. 45 (2022) 1485–1500.
https://doi.org/10.2989/16073606.2021.1950862
K.F. Roth, On a problem of Heilbronn, J. London Math. Soc. (1) 26 (1951) 198–204.
https://doi.org/10.1112/jlms/s1-26.3.198
R. Schrader and L. Stenmans, A de {B}ruijn-{E}rdős theorem for $(q,q - 4)$-graphs, Discrete Appl. Math. 279 (2020) 198–201.
https://doi.org/10.1016/j.dam.2019.11.008
M.G.S. Thankachy, U. Chandran S.V., J. Tuite, E.J. Thomas, G. Di Stefano and G. Erskine, On the vertex position number of graphs, Discuss. Math. Graph Theory(2023), in press.
https://doi.org/10.7151/dmgt.2491
E.J. Thomas and U. Chandran S.V., Characterization of classes of graphs with large general position number, AKCE Int. J. Graphs Comb. 17 (2020) 935–939.
https://doi.org/10.1016/j.akcej.2019.08.008
E.J. Thomas, U. Chandran S.V., J. Tuite and G. Di Stefano, On monophonic position sets of graphs, Discrete Appl. Math.(2023), in press.
https://doi.org/10.1016/j.dam.2023.02.021
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
J. Tuite, E.J. Thomas and U. Chandran S.V., On some extremal position problems for graphs, Ars Math. Contemp.(2023), in press.
https://doi.org/10.26493/1855-3974.3094.bc6
Y. Yao, M. He and S. Ji, On the general position number of two classes of graphs, Open Math. 20 (2022) 1021–1029.
https://doi.org/10.1515/math-2022-0444