Đồ thị bánh xe

Bách khoa toàn thư mở Wikipedia
Jump to navigation Jump to search
Đồ 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:
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) được tạo thành từ đồ thị chu trình 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. chu trình đơn(dãy số A002061 trong bảng OEIS).

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

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

.

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]