| Full text | |
| Author(s): |
Botler, Fabio
;
Hoppen, Carlos
;
Mota, Guilherme Oliveira
;
Ferreira, CE
;
Lee, O
;
Miyazawa, FK
Total Authors: 6
|
| Document type: | Journal article |
| Source: | PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM; v. 195, p. 9-pg., 2021-01-01. |
| Abstract | |
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) | |
| FAPESP's process: | 18/04876-1 - Ramsey theory, structural graph theory and applications in Bioinformatics |
| Grantee: | Guilherme Oliveira Mota |
| Support Opportunities: | Research Grants - Young Investigators Grants |
| FAPESP's process: | 19/13364-7 - Extremal and structural problems in graph theory |
| Grantee: | Cristina Gomes Fernandes |
| Support Opportunities: | Regular Research Grants |