Mutual-visibility problems in Kneser and Johnson graphs

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

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.

• Jezik: Angleški jezik
• Ključne besede: mutual-visibility set, total mutual-visibility set, Kneser graph, bipartite Kneser graph, Johnson graph, Turán-type problem, covering design
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Datum objave: 01.01.2025
• Leto izida: 2025
• Št. strani: 16 str.
• Številčenje: Vol. 25, no. 3, article no. P3.07
• PID: 20.500.12556/RUL-180300
• UDK: 519.17
• ISSN pri članku: 1855-3966
• DOI: 10.26493/1855-3974.3344.4c8
• COBISS.SI-ID: 270605059
• Datum objave v RUL: 05.03.2026

Gradivo je del revije

• Naslov: Ars mathematica contemporanea
• Založnik: 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

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: množica vzajemne vidnosti, množica celotne vzajemne vidnosti, Kneserjev graf, dvodelni Kneserjev graf, Johnsonov graf, problem Turánovega tipa, pokrivni načrt