Đồ 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: |
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. có chu trình đơn(dãy số A002061 trong bảng OEIS).
Đa thức màu của đồ thị là:
Xem thêm
Chú thích
- ^ Weisstein, Eric W., "Wheel Graph", MathWorld.
Tham khảo
Liên kết ngoài
Bài viết này vẫn còn sơ khai. Bạn có thể giúp Wikipedia mở rộng nội dung để bài được hoàn chỉnh hơn.
|