DEFESA DE TESE DE DOUTORADO Nº 32

Aluno: Mateus Alves Martins

Título: “Recursive calculation for lexicographic graph powers of a function related to the Hall ratio”

Orientador: João Fausto Lorenzato de Oliveira

Coorientador: Pablo Vinicius Alves de Barros ()

Examinador Externo: Carlile Campos Lavor (UNICAMP)

Examinador Externo: Fabricio Cristófani (FITec)

Examinador Externo: Maurício Costa Goldfarb (UPE)

Examinador Interno: Carmelo Albanez Bastos Junior

Data-hora: 27 de agosto de 2025 às 14h

Local: Formato remoto - Google Meet

---

Resumo:

         ""Given a graph G and an integer a satisfying 1 ≤ a ≤ α(G) = vertex independence number of G, we define w(a,G) = max {|V(H)| ; H is a subgraph of G and α(H) = a}. The w-function is connected to the Hall ratio, ρ(G) = max { |V(H)| / α(H) ; H is a subgraph of G }. The connection is: ρ(G) = max_a w(a,G) / a. It has proven to be surprisingly difficult to analyze the behavior of the Hall ratio with respect to various graph operations, in particular, the various graph products and the Mycielskian transformation. In this work we give a way of recursively calculating w(a,Gⁿ), where the power of G is taken with respect to the lexicographic product. The process is illustrated in the case where G = W₅, the wheel with 5 spokes."