Граф-веер

Веерный граф

В теории графов веерный граф (также называемый веерным графом пути) — это граф, образованный соединением графа-пути и пустого графа с одной вершиной. Веерный граф с $n+1$ вершиной, обозначаемый $F_n$, определяется как $K_1+P_n$, где $K_1$ — одиночная вершина, а $P_n$ — путь с $n$ вершинами.

Веерный граф $F_n$ имеет $n+1$ вершину и $2n-1$ рёбер.

Насыщенность

Граф $G$ является $H$-насыщенным, если он не содержит $H$ в качестве подграфа, но добавление любого ребра $e\notin E(G)$ приводит к появлению хотя бы одной копии $H$ в качестве подграфа. Число насыщенности $\text{sat}(n,H)$ — это минимальное количество рёбер в $H$-насыщенном графе на $n$ вершинах, в то время как задача о запрещённом подграфе $\text{ex}(n,H)$ — это максимально возможное количество рёбер в графе $G$ на $n$ вершинах, который не содержит копии $H$.

$t$-веер (иногда называемый графом дружбы), $F_t(t\ge 2)$, — это граф, состоящий из $t$ непересекающихся по рёбрам треугольников, которые пересекаются в одной вершине $v$.

Число насыщенности для $F_t$ равно $\text{sat}(n,F_t)=n+3t-4$ для $t\ge 2$ и $n\ge 3t-2$.

Раскраска графов

Упаковочное хроматическое число ${\chi }_{\rho }(G)$ графа $G$ — это наименьшее целое число $k$, для которого существует отображение $\pi :V(G)\to 1,2,\dots ,k$ такое, что любые две вершины цвета $i$ находятся на расстоянии не менее $i+1$. Упаковочное хроматическое число изучалось для различных графов, связанных с веерами и колесами.

См. также

• Колесный граф
• Операции над графами
• Граф дружбы

Ссылки

• https://www.researchgate.net/publication/311394521_Packing_chromatic_number_of_certain_fan_and_wheel_related_graphs