On the general position problem on Kneser graphs

DOI10.26493/1855-3974.1957.A0FMaRDI QIDQ4988852zbMATH OpenOpenAlexFDO

Authors Balázs Patkós

Publication date 19 May 2021

Published in Ars Mathematica Contemporanea (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1903.08056

zbMATH Keywords

general position problemintersection theoremsKneser graphs

Mathematics Subject Classification ID

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

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 $nge{k}^3-k^2+2k-2$, then $$, where $K{n}_{n,k}$ denotes the Kneser graph. We improve on their result and show that the same conclusion holds for $nge2.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.

Recommendations

• The general position problem on Kneser graphs and on some graph operations
• Characterization of classes of graphs with large general position number
• The graph theory general position problem on some interconnection networks
• A general position problem in graph theory
• The odd girth of the generalised Kneser graph

Cites work

• A general position problem in graph theory
• Almost Intersecting Families of Sets
• Characterization of general position sets and its applications to cographs and bipartite graphs
• Extremal G-free induced subgraphs of Kneser graphs
• Finding points in general position
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• On generalized graphs
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Sperner capacities
• Stability results for vertex Turán problems in Kneser graphs
• The general position problem on Kneser graphs and on some graph operations

Cited in

(42)

• On general position sets in Cartesian products
• The general position problem on Kneser graphs and on some graph operations
• Bollobás-type theorems for hemi-bundled two families
• On the general position number of two classes of graphs
• The edge general position problem
• On the mutual visibility in Cartesian products and triangle-free graphs
• The general position achievement game played on graphs
• The general position number of Cartesian products involving a factor with small diameter
• A Steiner general position problem in graph theory
• On the General Position Number of Complementary Prisms
• The general position number of the Cartesian product of two trees
• General d-position sets
• On independent position sets in graphs
• Variety of mutual-visibility problems in graphs
• TRAVERSING A GRAPH IN GENERAL POSITION
• Total mutual-visibility in graphs with emphasis on lexicographic and Cartesian products
• On the general position numbers of maximal outerplane graphs
• Some position problems for graphs
• Edge general position sets in Fibonacci and Lucas cubes
• Extremal edge general position sets in some graphs
• The general position avoidance game and hardness of general position games
• General position polynomials
• On monophonic position sets in graphs
• All-path convexity: two characterizations, general position number, and one algorithm
• Mutual-visibility problems on graphs of diameter two
• Mutual-visibility in strong products of graphs via total mutual-visibility
• On the general position number of the k -th power graphs
• A note on the edge general position number of cactus graphs
• General position problems in strong and lexicographic products of graphs
• General position sets, colinear sets, and Sierpiński product graphs
• Counting largest mutual-visibility and general position sets of glued t-ary trees
• The general position number under vertex and edge removal
• Characterizing and computing in linear time mutual-visibility parameters in distance-hereditary graphs
• Mutual-visibility problems in Kneser and Johnson graphs
• The edge general position number of some graphs
• Graphs whose edge general position number is 4
• Lower general position sets in graphs
• Graphs with total mutual-visibility number zero and total mutual-visibility in Cartesian products
• On the vertex position number of graphs
• The iteration time and the general position number in graph convexities
• Generalization of edge general position problem
• Builder-blocker general position games

This page was built for publication: On the general position problem on Kneser graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4988852)