Abstract | ||
---|---|---|
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 gp(G). Recently, Ghorbani et al. proved that for any k if n >= k(3) - k(2) + 2k - 2, then gp(Kn(n, k)) = ((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 >= 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 Bollobas's inequality on intersecting set pair systems. |
Year | DOI | Venue |
---|---|---|
2020 | 10.26493/1855-3974.1957.a0f | ARS MATHEMATICA CONTEMPORANEA |
Keywords | DocType | Volume |
General position problem, Kneser graphs, intersection theorems | Journal | 18 |
Issue | ISSN | Citations |
2 | 1855-3966 | 0 |
PageRank | References | Authors |
0.34 | 0 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Balázs Patkós | 1 | 85 | 21.60 |