Đồ 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).

Tập tin:CyclesW4.svg

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))$