Convexidade cíclica em grafos

Convexidades em grafos são inspiradas no conceito de mesmo nome em geometria mas adaptadas para esse contexto. Diferentes definições do que constitui um conjunto convexo já foram estudadas, entre as mais conhecidas estão aquelas definidas sobre caminhos, como as convexidades P3 e geodética. Além do interesse teórico, processos como a propagação de informações ou epidemias podem ser modelados por conceitos de convexidade em grafos – estruturas que capturam regras de influência em redes sociais complexas. Nesses contextos, as regras de propagação estão diretamente relacionadas com uma definição de uma convexidade em grafos e o objeto de estudo se torna a função de intervalo da convexidade, que é o conceito análogo à combinação convexa, da geometria. Neste trabalho, abordamos a convexidade cíclica, inicialmente motivada por aplicações em teoria dos nós. Formalmente, dado um grafo G e um subconjunto S ⊆ G, a função de intervalo infecta v ̸∈ S se existe um ciclo em G[S ∪ {v}]. Alguns aspectos dessa convexidade já foram estudados, com resultados recentes sobre seus números de intervalo e de convexidade. Nosso objetivo é responder uma terceira questão de interesse na área de convexidade em grafos para a convexidade cíclica, que chamamos de Partição em Conjuntos Convexos Cíclicos (PCCC): dado um grafo G e um inteiro k, é possível particionar G em exatamente k conjuntos convexos? Nossos resultados contribuem para a compreensão da estrutura dos conjuntos convexos cíclicos e abrem caminho para o desenvolvimento de algoritmos eficientes em classes específicas de grafos.