Geodesic
The General Position Problem on Kneser Graphs and on Some Graph Operations
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 4, pp. 1199-1213.

Voir la notice de l'article provenant de la source Library of Science

A vertex subset S of a graph G is a general position set of G if no vertex of S lies on a geodesic between two other vertices of S. The cardinality of a largest general position set of G is the general position number (gp-number) gp(G) of G. The gp-number is determined for some families of Kneser graphs, in particular for K(n, 2), n ≥ 4, and K(n, 3), n ≥ 9. A sharp lower bound on the gp-number is proved for Cartesian products of graphs. The gp-number is also determined for joins of graphs, coronas over graphs, and line graphs of complete graphs.
Keywords: general position set, Kneser graphs, Cartesian product of graphs, corona over graphs, line graphs 
@article{DMGT_2021_41_4_a21,
     author = {Ghorbani, Modjtaba and Maimani, Hamid Reza and Momeni, Mostafa and Mahid, Farhad Rahimi and Klav\v{z}ar, Sandi and Rus, Gregor},
     title = {The {General} {Position} {Problem} on {Kneser} {Graphs} and on {Some} {Graph} {Operations}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1199--1213},
     publisher = {mathdoc},
     volume = {41},
     number = {4},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a21/}
}
TY  - JOUR
AU  - Ghorbani, Modjtaba
AU  - Maimani, Hamid Reza
AU  - Momeni, Mostafa
AU  - Mahid, Farhad Rahimi
AU  - Klavžar, Sandi
AU  - Rus, Gregor
TI  - The General Position Problem on Kneser Graphs and on Some Graph Operations
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 1199
EP  - 1213
VL  - 41
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a21/
LA  - en
ID  - DMGT_2021_41_4_a21
ER  - 
%0 Journal Article
%A Ghorbani, Modjtaba
%A Maimani, Hamid Reza
%A Momeni, Mostafa
%A Mahid, Farhad Rahimi
%A Klavžar, Sandi
%A Rus, Gregor
%T The General Position Problem on Kneser Graphs and on Some Graph Operations
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 1199-1213
%V 41
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a21/
%G en
%F DMGT_2021_41_4_a21
Ghorbani, Modjtaba; Maimani, Hamid Reza; Momeni, Mostafa; Mahid, Farhad Rahimi; Klavžar, Sandi; Rus, Gregor. The General Position Problem on Kneser Graphs and on Some Graph Operations. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 4, pp. 1199-1213. http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a21/

[1] B.S. Anand, S.V. Ullas Chandran, 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] G. Boruzanli Ekinci and J.B. Gauci, The super-connectivity of Kneser graphs, Discuss. Math. Graph Theory 39 (2019) 5–11. https://doi.org/10.7151/dmgt.2051

[3] B. Brešar and M. Valencia-Pabon, Independence number of products of Kneser graphs, Discrete Math. 342 (2019) 1017–1027. https://doi.org/10.1016/j.disc.2018.12.017

[4] K.N. Chadha and A.A. Kulkarni, On independent cliques and linear complementarity problems (2018). arXiv:1811.09798

[5] H.E. Dudeney, Amusements in Mathematics (Nelson, Edinburgh, 1917).

[6] P. Erdős, C. Ko and R. Rado, Intersection theorems for systems of finite sets, Q. J. Math. 12 (1961) 313–320. https://doi.org/10.1093/qmath/12.1.313

[7] V. Froese, I. Kanj, A. Nichterlein and R. Niedermeier, Finding points in general position, Internat. J. Comput. Geom. Appl. 27 (2017) 277–296. https://doi.org/10.1142/S021819591750008X

[8] W. Imrich, S. Klavžar and D.F. Rall, Topics in Graph Theory: Graphs and Their Cartesian Product (A K Peters, New York 2008). https://doi.org/10.1201/b10613

[9] M.M. Kanté, R.M. Sampaio, V.F. dos Santos and J.L. Szwarcfiter, On the geodetic rank of a graph, J. Comb. 8 (2017) 323–340. https://doi.org/10.4310/JOC.2017.v8.n2.a5

[10] S. Klavžar, B. Patkós, G. Rus and I.G. Yero, On general position sets in Cartesian grids (2019). arXiv:1907.04535v3

[11] 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

[12] C.Y. Ku and K.B. Wong, On no-three-in-line problem on m-dimensional torus, Graphs Combin. 34 (2018) 355–364. https://doi.org/10.1007/s00373-018-1878-8

[13] J.H. van Lint and R.M. Wilson, A Course in Combinatorics (Cambridge University Press, Cambridge, 1992). https://doi.org/10.1017/CBO9780511987045

[14] 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

[15] P. Manuel and S. Klavžar, The graph theory general position problem on some interconnection networks, Fund. Inform. 163 (2018) 339–350. https://doi.org/10.3233/FI-2018-1748

[16] A. Misiak, Z. St¸epień, A. Szymaszkiewicz, L. Szymaszkiewicz and M. Zwierzchowski, A note on the no-three-in-line problem on a torus, Discrete Math. 339 (2016) 217–221. https://doi.org/10.1016/j.disc.2015.08.006

[17] T. Mütze and P. Su, Bipartite Kneser graphs are Hamiltonian, Combinatorica 37 (2017) 1207–1219. https://doi.org/10.1007/s00493-016-3434-6

[18] B. Patkós, On the general position problem on Kneser graphs (2019). arXiv:1903.08056v2

[19] M. Payne and D.R. Wood, On the general position subset selection problem, SIAM J. Discrete Math. 27 (2013) 1727–1733. https://doi.org/10.1137/120897493

[20] A. Por and D.R. Wood, No-three-in-line-in- 3 D, Algorithmica 47 (2007) 481–488. https://doi.org/10.1007/s00453-006-0158-9

[21] S.V. Ullas Chandran and G. Jaya Parthasarathy, The geodesic irredundant sets in graphs, Int. J. Math. Combin. 4 (2016) 135–143. https://doi.org/10.5281/zenodo.826834

[22] M. Valencia-Pabon and J.-C. Vera, On the diameter of Kneser graphs, Discrete Math. 305 (2005) 383–385. https://doi.org/10.1016/j.disc.2005.10.001