 Geodetic convexity and kneser graphsMarcos Bedo, João V.S. Leite, Rodolfo A. Oliveira and Fábio Protti Applied Mathematics and Computation, 2023, vol. 449, issue C Abstract: The Kneser graphK(2n+k,n), for n≥1 and k≥0, is the graph G=(V,E) such that V={S⊆{1,…,2n+k}:|S|=n} and there is an edge uv∈E whenever u∩v=∅. Kneser graphs have a nice combinatorial structure, and many parameters have been determined for them, such as the diameter, the chromatic number, the independence number, and, recently, the hull number (in the context of P3-convexity). However, the determination of geodetic convexity parameters in Kneser graphs still remained open. In this work, we investigate both the geodetic number and the geodetic hull number of Kneser graphs. We give upper bounds and determine the exact value of these parameters for Kneser graphs of diameter two (which form a nontrivial subfamily). We prove that the geodetic hull number of a Kneser graph of diameter two is two, except for K(5,2), K(6,2), and K(8,3), which have geodetic hull number three. We also contribute to the knowledge on Kneser graphs by presenting a characterization of endpoints of diametral paths in K(2n+k,n), used as a tool for obtaining some of the main results in this work. Keywords: Kneser graphs; Geodetic convexity; Hull number (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:449:y:2023:i:c:s0096300323001339 DOI: 10.1016/j.amc.2023.127964 Access Statistics for this article Applied Mathematics and Computation is currently edited by Theodore Simos More articles in Applied Mathematics and Computation from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.