| Texto completo | |
| Autor(es): |
Botler, Fabio
;
Hoppen, Carlos
;
Mota, Guilherme Oliveira
;
Ferreira, CE
;
Lee, O
;
Miyazawa, FK
Número total de Autores: 6
|
| Tipo de documento: | Artigo Científico |
| Fonte: | PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM; v. 195, p. 9-pg., 2021-01-01. |
| Resumo | |
Let S-k(n) be the maximum number of orientations of an n-vertex graph G in which no copy of K-k is strongly connected. For all integers n, k >= 4 where n >= 5 or k >= 5, we prove that S-k(n) = 2(tk-1(n)) where t(k-1)(n) is the number of edges of the n -vertex (k 1) -partite Turan graph Tk-1(n). Moreover, we prove that Tk-1(n) is the only graph having 2(tk-1(n)) orientations with no strongly connected copies of K-k. (C) 2021 The Authors. Published by Elsevier B.V. (AU) | |
| Processo FAPESP: | 18/04876-1 - Teoria de Ramsey, teoria estrutural de grafos e aplicações em Bioinformática |
| Beneficiário: | Guilherme Oliveira Mota |
| Modalidade de apoio: | Auxílio à Pesquisa - Jovens Pesquisadores |
| Processo FAPESP: | 19/13364-7 - Problemas extremais e estruturais em teoria dos grafos |
| Beneficiário: | Cristina Gomes Fernandes |
| Modalidade de apoio: | Auxílio à Pesquisa - Regular |