On the general position problem on Kneser graphs

Balazs Patkos

Abstract


In a graph G, a between two vertices x and y is a shortest path connecting x to y. A subset S of the vertices of G is 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 that we denote by gp(G). Recently, Ghorbani et al, proved that for any k if n ≥ k3 − k2 + 2k − 2, then $gp(Kn_{n,k})=\binom{n-1}{k-1}$, where Knn, k denotes the Kneser graph. We improve on their result and show that the same conclusion holds for n ≥ 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'as’s inequality on intersecting set pair systems.


Keywords


General position sets, Kneser graphs, intersection theorems.

Full Text:

MANUSCRIPT


ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications