Đồ thị bánh xe

Đồ thị bánh xe

Ví dụ về các đồ thị bánh xe

số đỉnh: n+1

số cạnh: 2n

đường kính: 2 nếu n > 4, 1 nếu n=4

chu trình ngắn nhất: 3

ký hiệu: $W_{n}$

sắc số: 4 nếu n chẵn, 3 nếu n lẻ

số màu cạnh: n-1

tính chất khác đồ thị phẳng đồ thị Hamilton

Trong lý thuyết đồ thị, đồ thị bánh xe (tiếng Anh: wheel graph) $W_{n}$ được tạo thành từ đồ thị chu trình $C_{n-1}$ bằng cách thêm 1 đỉnh và các cạnh nối đỉnh đó với tất cả các đỉnh còn lại.

Đồ thị bánh xe là đồ thị Hamilton. $W_{n}$ có $n^{2}-3n+3$ chu trình đơn(dãy số A002061 trong bảng OEIS).

7 chu trình đơn trong đồ thị W₄.

Đa thức màu của đồ thị $W_{n}$ là:

$P_{W_{n}}(x)=x((x-2)^{(n-1)}-(-1)^{n}(x-2))$