| Full text | |
| Author(s): |
Botler, Fabio
;
Hoppen, Carlos
;
Mota, Guilherme Oliveira
Total Authors: 3
|
| Document type: | Journal article |
| Source: | DISCRETE MATHEMATICS; v. 345, n. 12, p. 13-pg., 2022-08-05. |
| 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), and that Tk-1 (n) is the only n-vertex graph with this number of orientations. Furthermore, S-4(4) = 40 and this maximality is achieved only by K-4. (C) 2022 Elsevier B.V. All rights reserved. (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 |