×

On the general position problem on Kneser graphs. (English) Zbl 1464.05136

Summary: In a graph \(G\), a geodesic between two vertices \(x\) and \(y\) is a shortest path connecting \(x\) to \(y\). A subset \(S\) of the vertices of \(G\) is in general position if no vertex of \(S\) lies on any geodesic between two other vertices of \(S\). The size of a largest set of vertices in general position is the general position number that we denote by \(\operatorname{gp}(G)\). Recently, M. Ghorbani et al. [Discuss. Math., Graph Theory 41, No. 4, 1199–1213 (2021; Zbl 1468.05057)] proved that for any \(k\) if \(n\geq k^3-k^2+2k-2\), then \(\operatorname{gp}(Kn_n,k)=\binom{n -1}{k-1}\), where \(Kn_{n,k}\) denotes the Kneser graph. We improve on their result and show that the same conclusion holds for \(n\geq 2.5k-0.5\) and this bound is best possible. Our main tools are a result on cross-intersecting families and a slight generalization of Bollobás’s inequality on intersecting set pair systems.

MSC:

05C12 Distance in graphs
05C38 Paths and cycles
05C35 Extremal problems in graph theory

Citations:

Zbl 1468.05057

References:

[1] M. Alishahi and A. Taherkhani, ExtremalG-free induced subgraphs of Kneser graphs,J. Comb. Theory Ser. A159(2018), 269-282, doi:10.1016/j.jcta.2018.06.010. · Zbl 1392.05108
[2] B. S. Anand, U. Chandran S. V., M. Changat, S. Klavˇzar and E. J. Thomas, Characterization of general position sets and its applications to cographs and bipartite graphs,Appl. Math. Comput. 359(2019), 84-89, doi:10.1016/j.amc.2019.04.064. · Zbl 1428.05078
[3] B. Bollob´as, On generalized graphs,Acta Math. Acad. Sci. Hungar.16(1965), 447-452, doi: 10.1007/bf01904851. · Zbl 0138.19404
[4] S. V. Chandran and G. J. Parthasarathy, The geodesic irredundant sets in graphs,Int. J. Math. Comb.4(2016), 135-143,http://fs.unm.edu/IJMC/IJMC-4-2016.pdf.
[5] P. Erd˝os, C. Ko and R. Rado, Intersection theorems for systems of finite sets,Quart. J. Math. Oxford12(1961), 313-320, doi:10.1093/qmath/12.1.313. · Zbl 0100.01902
[6] V. Froese, I. Kanj, A. Nichterlein and R. Niedermeier, Finding points in general position,Internat. J. Comput. Geom. Appl.27(2017), 277-296, doi:10.1142/s021819591750008x. · Zbl 1386.68196
[7] L. Gargano, J. K¨orner and U. Vaccaro, Sperner capacities,Graphs Combin.9(1993), 31-46, doi:10.1007/bf01195325. · Zbl 0771.05004
[8] D. Gerbner, N. Lemons, C. Palmer, B. Patk´os and V. Sz´ecsi, Almost intersecting families of sets,SIAM J. Discrete Math.26(2012), 1657-1669, doi:10.1137/120878744. · Zbl 1261.05126
[9] D. Gerbner, A. Methuku, D. T. Nagy, B. Patk´os and M. Vizer, Stability results for vertex Tur´an problems in Kneser graphs,Electron. J. Combin.26(2019), #P2.13 (12 pages), doi:10.37236/ 8130. · Zbl 1410.05213
[10] M. Ghorbani, H. R. Maimani, M. Momeni, F. R. Mahid, S. Klavˇzar and G. Rus, The general position problem on kneser graphs and on some graph operations,Discuss. Math. Graph Theory (2020), doi:10.7151/dmgt.2269. · Zbl 1468.05057
[11] A. J. W. Hilton and E. C. Milner, Some intersection theorems for systems of finite sets,Quart. J. Math. Oxford18(1967), 369-384, doi:10.1093/qmath/18.1.369. · Zbl 0168.26205
[12] P. Manuel and S. Klavˇzar, A general position problem in graph theory,Bull. Aust. Math. Soc. 98(2018), 177-187, doi:10.1017/s0004972718000473. · Zbl 1396.05033
[13] J.O’NeillandJ.Verstraete,Bollob´as-typeinequalitiesonsetk-tuples,2018, arXiv:1812.00537v1[math.CO].
[14] A. R´enyi,Foundations of Probability, Wiley, 1971.
[15] A. Taherkhani, Size and structure of large(s, t)-union intersecting families, 2019, arXiv:1903.02614[math.CO].
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.