The general position achievement game played on graphs

Klavžar, Sandi (author), Neethu, P.K. (author), Ullas Chandran, S.V. (author)

A general position set of a graph G is a set of vertices S in G such that no three vertices from S lie on a common shortest path. In this paper we introduce and study the general position achievement game. The game is played on a graph G by players A and B who alternatively pick vertices of G. A selection of a vertex is legal if has not been selected before and the set of vertices selected so far forms a general position set of G. The player who selects the last vertex wins the game. Playable vertices at each step of the game are described, and sufficient conditions for each of the players to win is given. The game is studied on Cartesian and lexicographic products. Among other results it is proved that A wins the game on K$_n$ □ K$_m$ if and only if both n and m are odd, and that B wins the game on G ∘ K$_n$ if and only if either B wins on G or n is even.

• Language: English
• Keywords: general position set, achievement game, Cartesian product of graphs, lexicographic product of graphs
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Year: 2022
• Number of pages: Str. 109-116
• Numbering: Vol. 317
• PID: 20.500.12556/RUL-139072
• UDC: 519.17
• ISSN on article: 0166-218X
• DOI: 10.1016/j.dam.2022.04.019
• COBISS.SI-ID: 108461571
• Publication date in RUL: 30.08.2022

KLAVŽAR, Sandi, NEETHU, P.K. and ULLAS CHANDRAN, S.V., 2022, The general position achievement game played on graphs. Discrete applied mathematics [online]. 2022. Vol. 317, p. 109–116. [Accessed 9 April 2025]. DOI 10.1016/j.dam.2022.04.019. Retrieved from: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=eng&id=139072

Record is a part of a journal

• Title: Discrete applied mathematics
• Shortened title: Discrete appl. math.
• Publisher: Elsevier
• ISSN: 0166-218X
• COBISS.SI-ID: 25342464

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 v splošni legi, igra doseganja, kartezični produkt grafov, leksikografski produkt grafov