Một điều kiện mới để một đồ thị có số liên thông không xung đột là 2

0 Người đánh giá. Xếp hạng trung bình 0

Tác giả: Ngọc Diệp Phạm

Ngôn ngữ: Vie

Ký hiệu phân loại:

Thông tin xuất bản: Khoa học (Đại học Sư phạm Hà Nội) 2021

Mô tả vật lý: 25-39

Bộ sưu tập: Metadata

ID: 405248

Thêm vào giỏ Liên kết toàn văn

Trong đồ thị có các cạnh được tô màu, một đường được gọi là không xung đột nếu có màu được sử dụng trên các cạnh của đường đó duy nhất một lần. Một đồ thị có các cạnh được tô màu được gọi là đồ thị liên thông không xung đột nếu hai đỉnh bất kì của đồ thị được nối với nhau bởi ít nhất một đường liên thông không xung đột. Đặt cfc(G) là số màu nhỏ nhất sao cho ta có thể dùng các màu đó để tô các cạnh của đồ thị G sao cho G là đồ thị liên thông không xung đột. Trong bài báo này, chúng tôi sẽ đưa ra một điều kiện về bậc nhỏ nhất của đồ thị liên thông không đầy đủ G để G có cfc(G) = 2. Kết quả đạt được là một mở rộng của một kết quả trong bài báo [1] của Chang và các cộng sự., Tóm tắt tiếng anh, A path in an edge-coloured graph is called conflict-free if there is a colour used on exactly one of its edges. An edge-coloured graph is said to be conflict-free connected if any two distinct vertices of the graph are connected by a conflict-free path. The conflict-free connection number, denoted by cfc(G), is the smallest number of colours needed in order to make G conflict-free connected. In this paper, we give a new condition to show that a connected non-complete graph G having cfc(G) = 2. This is an extension of a result by Chang et al. [1].

1. Đọc trực tuyến

1. Đọc trực tuyến

Tạo bộ sưu tập với mã QR