Đồ 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: ${\displaystyle 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) ${\displaystyle W_{n}}$ được tạo thành từ đồ thị chu trình ${\displaystyle 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. ${\displaystyle W_{n}}$ có ${\displaystyle 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ị ${\displaystyle W_{n}}$ là:

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

Xem thêm

Chú thích

1. Weisstein, Eric W., "Wheel Graph", MathWorld.

Tham khảo

Liên kết ngoài