Sobre o número envoltório para prismas complementares de grafos conexos $G$ e $\overline{G}$

- 84673
Artigo Completo
Favoritar este trabalho
Como citar esse trabalho?
Resumo

Na convexidade geodética, um conjunto de vértices $S$ de um grafo $G$ é \textit{convexo} se todos os vértices de todo caminho mínimo entre dois vértices de $S$ pertencem a $S$. O \textit{fecho convexo} $H(S)$ de $S$ é o menor conjunto convexo contendo $S$. Se $H(S) = V(G)$, então $S$ é um \textit{conjunto envoltório} de $G$. A cardinalidade $h(G)$ de um conjunto envoltório mínimo em $G$ é o \textit{número envoltório} de $G$. O prisma complementar $G\overline{G}$ de $G$ é o grafo da união disjunta de $G \cup \overline{G}$, adicionando arestas para um emparelhamento perfeito entre os vértices correspondentes de $G$ e $\overline{G}$. Motivados por trabalhos anteriores, estudamos o número envoltório para prismas complementares quando ambos $G$ e $\overline{G}$ são conexos. Quando $G$ é um grafo split, mostramos que o número envoltório é ilimitado. Caso contrário, quando $G$ não é um grafo split, é limitado a $3$.

Instituições
  • 1 Universidade Federal de Goiás
Eixo Temático
  • TAG – Teoria e Algoritmos em Grafos
Palavras-chave
Geodetic convexity
hull number
complementary prisms