Builder-Blocker Mutual-Visibility Game

Creative Commons License

Chenoweth V. I., Klavžar S., Rus G., TAN E., Tian J.

Bulletin of the Malaysian Mathematical Sciences Society, cilt.49, sa.2, 2026 (SCI-Expanded, Scopus) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 49 Sayı: 2
  • Basım Tarihi: 2026
  • Doi Numarası: 10.1007/s40840-026-02083-9
  • Dergi Adı: Bulletin of the Malaysian Mathematical Sciences Society
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, MathSciNet, zbMATH
  • Anahtar Kelimeler: Complete multipartite graph, Games on graphs, Hamming graph, Mutual-visibility set
  • Ankara Üniversitesi Adresli: Evet

Özet

This article discusses mutual-visibility in graphs through a game-based version of the problem. Two players, Builder and Blocker, alternately select an unmarked vertex on a graph keeping the property that the set of marked vertices forms a mutual-visibility set. The game ends when no such selection is possible. The goal of Builder is to create a largest possible mutual-visibility set, Blocker’s goal is the opposite. The central problem here is to determine the number of vertices selected during the game assuming that both players played optimally. Bounds on this number are proved and several general properties of the game derived. Special attention is paid to complete multipartite graphs and Hamming graphs.