Department of
Applied
Mathematics

LIFO-search on Graphs and Digraphs

Archontia Giannopoulou

National Kapodistrian University of Athens

Abstract

In this talk we discuss some game characterizations of graph parameters and, in particular, a variant of the classic node search game called LIFO-search where searchers are assigned different numbers. The additional rule is that now searchers carry ranks and a searcher can be removed from the graph only if no searchers of lower rank are in the graph at that moment.

We prove that all common variations of the game require the same number of searchers, the corresponding parameter is tree-depth and the game is monotone.

Furthermore, moving out of the world of simple graphs and into the world of digraphs the LIFO-search game is again monotone and the LIFO-search parameter is equivalent to cycle-rank.