Число помеченных внешнепланарных k-циклических графов

摘要

k-Циклический граф-это граф с цикломатическим числом, равным к. Получена явная формула для числа помеченных связных внешнепланарных к-циклических графов с заданным числом вершин. Кроме того, такие графы с фиксированным числом k и большим числом вершин перечислены асимптотически. Как следствие, выводится, что при фиксированном числе k почти все помеченные связные внешнепланарные k-циклические графы с большим числом вершин являются кактусами.