Đồ thị bánh xe

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm
Đồ thị bánh xe
Wheel graphs.svg
Ví dụ về các đồ thị bánh xe
số đỉnh: n
số cạnh: 2n-2
đườ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[1].

Đồ thị bánh xe là đồ thị Hamilton. W_nn^2-3n+3 chu trình đơn(dãy A002061 trong OEIS).

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

Đa thức màu của đồ thị W_n là:

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

.

Xem thêm[sửa | sửa mã nguồn]

Chú thích[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]

Liên kết ngoài[sửa | sửa mã nguồn]