Mutual-visibility problems in Kneser and Johnson graphs

Boruzanli Ekinci, Gülnaz (author), Bujtás, Csilla (author)

Let $G$ be a connected graph and $X \subseteq V(G)$. By definition, two vertices $u$ and $v$ are $X$-visible in $G$ if there exists a shortest $u, v$-path with all internal vertices being outside of the set $X$. The largest size of $X$ such that any two vertices of $G$ (resp. any two vertices from $X$) are $X$-visible is the total mutual-visibility number (resp. the mutual-visibility number) of ▫$G$▫. In this paper, we determine the total mutual-visibility number of Kneser graphs, bipartite Kneser graphs, and Johnson graphs. The formulas proved for Kneser, and bipartite Kneser graphs are related to the size of transversal-critical uniform hypergraphs, while the total mutual-visibility number of Johnson graphs is equal to a hypergraph Turán number. Exact values or estimates for the mutual-visibility number over these graph classes are also established.

• Language: English
• Keywords: mutual-visibility set, total mutual-visibility set, Kneser graph, bipartite Kneser graph, Johnson graph, Turán-type problem, covering design
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Publication date: 01.01.2025
• Year: 2025
• Number of pages: 16 str.
• Numbering: Vol. 25, no. 3, article no. P3.07
• PID: 20.500.12556/RUL-180300
• UDC: 519.17
• ISSN on article: 1855-3966
• DOI: 10.26493/1855-3974.3344.4c8
• COBISS.SI-ID: 270605059
• Publication date in RUL: 05.03.2026

Record is a part of a journal

• Title: Ars mathematica contemporanea
• Publisher: Društvo matematikov, fizikov in astronomov, Društvo matematikov, fizikov in astronomov, Univerza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologije
• ISSN: 1855-3966
• COBISS.SI-ID: 239049984

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.

Secondary language

• Language: Slovenian
• Keywords: množica vzajemne vidnosti, množica celotne vzajemne vidnosti, Kneserjev graf, dvodelni Kneserjev graf, Johnsonov graf, problem Turánovega tipa, pokrivni načrt