Metric dimension of combinatorial game graphs

arXiv1905.05033MaRDI QIDQ6318643FDOQ6318643

Publication date: 13 May 2019

Abstract: The study of combinatorial games is intimately tied to the study of graphs, as any game can be realized as a directed graph in which players take turns traversing the edges until reaching a sink. However, there have heretofore been few efforts towards analyzing game graphs using graph theoretic metrics and techniques. A set

S

of vertices in a graph

G

resolves

G

if every vertex in

G

is uniquely determined by the vector of its distances from the vertices in

S

. A metric basis of

G

is a smallest resolving set and the metric dimension is the cardinality of a metric basis. In this article we examine the metric dimension of the graphs resulting from some rulesets, including both short games (those which are sure to end after finitely many turns) and loopy games (those games for which the associated graph contains cycles).

Mathematics Subject Classification ID

Distance in graphs (05C12) Combinatorial games (91A46)

This page was built for publication: Metric dimension of combinatorial game graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6318643)