On cycles, chords and kernels in digraphs

Author(s)

Alonso Ali Gonçalves

• Document type: Master's Dissertation
• Press: Campinas, SP.
• Institution: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Defense date: 2019-09-17

Examining board members

Orlando Lee; Christiane Neme Campos; Maycon Sambinelli

• Advisor: Orlando Lee

Abstract

A kernel is an independent and absorvent subset of vertices of a digraph. The conceptof kernel was introduced by von Neumann and Morgenstern in the game theory context with the intent of modeling social and economic interactions. The concept gained notoriety in the graph theory field because of its relation to the Perfect Graph Conjecture (now Strong Perfect Graphs Theorem) and its aplicability of finding winning strategies ingames. In this dissertation, we continue the study of suficient conditions for the existence of kernels and k-kernels in digraphs whose cycles have chords. We present the main results of the field, as well as new problems and results we got during the master¿s research (AU)

• FAPESP's process: 18/16720-6 - Kernel Theory in digraphs
• Grantee: Alonso Ali Gonçalves
• Support Opportunities: Scholarships in Brazil - Master