TAILIEUCHUNG - Báo cáo toán học: "Construction of Codes Identifying Sets of Vertices"

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Construction of Codes Identifying Sets of Vertices. | Construction of Codes Identifying Sets of Vertices Sylvain Gravier CNRS - UJF ERTé Maths à Modeler Groupe de Recherche GeoD Laboratoire Leibniz 46 avenue Felix Viallet 38031 Grenoble Cedex France Julien Moncel CNRS - UJF ERTé Maths à Modeler Groupe de Recherche GeoD Laboratoire Leibniz 46 avenue Felix Viallet 38031 Grenoble Cedex France Submitted Feb 8 2005 Accepted Mar 1 2005 Published Mar 8 2005 Mathematics Subject Classifications 05C99 94B60 94C12 Abstract In this paper the problem of constructing graphs having a 1 -identifying code of small cardinality is addressed. It is known that the cardinality of such a code is bounded by Q log log nỳ. Here we construct graphs on n vertices having a 1 -identifying code of cardinality O 4 log n for all 2. We derive our construction from a connection between identifying codes and superimposed codes which we describe in this paper. 1 Codes identifying sets of vertices Let G V E be a simple non-oriented graph. For a vertex v 2 V let us denote by N v the closed neighborhood of v N v N v u v . Let C Q V be a subset of vertices of G and for all nonempty subset of at most vertices X Q V let us denote I X I X C N x n C. x2X If all the I X C s are distinct then we say that C separates the sets of at most vertices of G and if all the I X C s are nonempty then we say that C covers the sets of at most vertices of G. We say that C is a code identifying sets of at most vertices of G if and only if C covers and separates all the sets of at most vertices of G. The dedicated terminology 12 for such codes is 1 Ế -identifying codes. The sets I X are said to be the identifying sets of the corresponding X s. THE ELECTRONIC JOURNAL OF COMBINATORICS 12 2005 R13 1 Whereas C V is trivially always a code covering the sets of at most vertices of any graph G V E not every graph has a 1 -identifying code. For example if G contains two vertices u and v such that N u N v then G has no 1 -identifying code .

TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN
TAILIEUCHUNG - Chia sẻ tài liệu không giới hạn
Địa chỉ : 444 Hoang Hoa Tham, Hanoi, Viet Nam
Website : tailieuchung.com
Email : tailieuchung20@gmail.com
Tailieuchung.com là thư viện tài liệu trực tuyến, nơi chia sẽ trao đổi hàng triệu tài liệu như luận văn đồ án, sách, giáo trình, đề thi.
Chúng tôi không chịu trách nhiệm liên quan đến các vấn đề bản quyền nội dung tài liệu được thành viên tự nguyện đăng tải lên, nếu phát hiện thấy tài liệu xấu hoặc tài liệu có bản quyền xin hãy email cho chúng tôi.
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.