In January 2023, I attended the Combinatorial Game Theory Colloquia, which was held in S. Miguel, Azores. What an awesome experience! The conference is held every other year and I’ll definitely be back. On the final day of the conference, I gave a talk titled Impartial geodetic convexity achievement and avoidance games on graphs. My talk summarized some of the work that was begun during my week at ICERM with Bret Benesh, Marie Meyer, Sarah Salmon, and Nandor Sieben. Nandor was also at the conference and gave a talk. Here is the abstract for my talk:

A set $P$ of vertices of a graph $G$ is convex if it contains all vertices along shortest paths between vertices in $P$. The convex hull of $P$ is the smallest convex set containing $P$. We say that a subset of vertices $P$ generates the graph $G$ if the convex hull of $P$ is the entire vertex set. We study two impartial games Generate and Do Not Generate in which two players alternately take turns selecting previously-unselected vertices of a finite graph $G$. The first player who builds a generating set for the graph from the jointly-selected elements wins the achievement game GEN($G$). The first player who cannot select a vertex without building a generating set loses the avoidance game DNG($G$). Similar games have been considered by several authors, including Harary et al. In this talk, we determine the nim-number for several graph families, including trees, cycle graphs, complete graphs, complete bipartite graphs, and hypercube graphs.

And here are the slides:

One cool consequence of the conference is that Nandor and I are now working on a new research project with Bojan Bašić, Paul Ellis, and Danijela Popović. The project was inspired by Danijela’s talk at the conference. I’m really excited about this new project!

Dana C. Ernst

Mathematics & Teaching

  Northern Arizona University
  Flagstaff, AZ
  Google Scholar
  Impact Story

Current Courses

  MAT 226: Discrete Math
  MAT 690: CGT

About This Site

  This website was created using GitHub Pages and Jekyll together with Twitter Bootstrap.

  Unless stated otherwise, content on this site is licensed under a Creative Commons Attribution-Share Alike 4.0 International License.

  The views expressed on this site are my own and are not necessarily shared by my employer Northern Arizona University.

  The source code is on GitHub.

Land Acknowledgement

  Flagstaff and NAU sit at the base of the San Francisco Peaks, on homelands sacred to Native Americans throughout the region. The Peaks, which includes Humphreys Peak (12,633 feet), the highest point in Arizona, have religious significance to several Native American tribes. In particular, the Peaks form the Diné (Navajo) sacred mountain of the west, called Dook'o'oosłííd, which means "the summit that never melts". The Hopi name for the Peaks is Nuva'tukya'ovi, which translates to "place-of-snow-on-the-very-top". The land in the area surrounding Flagstaff is the ancestral homeland of the Hopi, Ndee/Nnēē (Western Apache), Yavapai, A:shiwi (Zuni Pueblo), and Diné (Navajo). We honor their past, present, and future generations, who have lived here for millennia and will forever call this place home.