P3-Carathéodory em Grafos Circulantes

Vol 56, 2024 - 309600
Trabalho completo (Oral)
Favoritar este trabalho
Como citar esse trabalho?
Resumo

A maximização de influência em redes é um problema de grande interesse em diversas
áreas, vários modelos foram propostos para analisar essa a difusão. A convexidade em grafos é um
desses modelos, contando com diversos parâmetros para analisar a dinâmica desse comportamento,
tais como número envoltória, Radon, intervalo entre outros. O número de Carathéodory é um
destes interessantes parâmetros, já demonstrado ser NP-Completo, de estudo do comportamento de
difusão de influência. Neste artigo trataremos do número de Carathéodory para grafos circulantes na
convexidade P3. Para grafos circulantes Cn({1, r}) com r = 2, nós determinamos que o número de
Carathéodory é c(Cn(1,2)) = 2, como consequência determinamos o número de Carathéodory
para a subclasse de grafos Potência de Ciclo, ou seja c(Ckn) = 2. Para Cn(1,r) com r>2 e n≥4r−2 demonstramos que c(Cn(1, r))≥⌊(2r+1)/3⌋
se 3∤(r+1) e caso contrário c(Cn(1, r)) ≥ 2(r+1)/3.

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!

Instituições
  • 1 Instituto de Informática da Universidade Federal de Goiás
  • 2 Instituto de Informática - Universidade Federal de Goiás
  • 3 Universidade Federal de Goiás
Eixo Temático
  • 19. TAG – Teoria e Algoritmos em Grafos
Palavras-chave
Grafos
Convexidade P3
Caratheódory