Аннотация
An open triangle is a simple, undirected graph consisting of three vertices and two edges. It is shown that the maximum number of induced open triangles in a graph on n vertices is given by (n2-1)⌊n2⌋⌈n2⌉. The maximum is achieved for the complete bipartite graph K⌊ n / 2 ⌋ , ⌈ n / 2 ⌉. The maximum expected number of open triangles in a uniform random graph on n vertices is observed to be asymptotically equivalent.
Язык оригинала | английский |
---|---|
Страницы (с-по) | 1927-1935 |
Число страниц | 9 |
Журнал | Optimization Letters |
Том | 13 |
Номер выпуска | 8 |
DOI | |
Состояние | Опубликовано - 1 ноя 2019 |