Есть ли какой-нибудь пример графа, кроме полного графа, где Diameter (G) = Radius (G)?

Question

Мы знаем, что для любого графа G Радиус (G) ≤ Диаметр (G) ⩽ 2 * Радиус (G). Мне было интересно, есть ли какой-либо график, кроме полного графика, где Радиус (G) = Диаметр (G).

Answer 1

Да. Дополнение к полному графику! Если все вершины не имеют ребер, оба значения D и R равны. Чтобы быть более точным, существует класс графов, которые называются вершинно-транзитивными графами . Очевидно, что их радиус и диаметр равны (см. ref ).