Abordagens Gulosas para Gold Grabbing em subclasses de grafos split

O Gold Grabbing Game é um jogo combinatório em grafos ponderados no qual dois jogadores removem vértices alternadamente, mantendo o grafo conexo e buscando maximizar a soma dos pesos obtidos. A literatura concentra-se em estratégias que garantem a vitória; a otimalidade, isto é, a maximização do ganho, permanece menos explorada. Investigamos aqui a estratégia gulosa. Mostramos que ela não é ótima em grafos split gerais, mas que, nos split completos CS(1,n) e CS(2,n) — estes últimos conhecidos como grafos livro —, a sequência que ela produz realiza o valor do jogo val(G). Como consequência, o primeiro jogador não perde quando o número de vértices é par.