TAILIEUCHUNG - Báo cáo toán học: "Structural Properties of Twin-Free Graphs"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Structural Properties of Twin-Free Graphs. | Structural Properties of Twin-Free Graphs Irene Charon GET - Telecom Paris CNRS - LTCI UMR 5141 46 rue Barrault 75634 Paris Cedex 13 - France charon@ Iiro Honkala Department of Mathematics - University of Turku FIN-20014 Turku - Finland honkala@ Olivier Hudry GET - Telecom Paris CNRS - LTCI UMR 5141 46 rue Barrault 75634 Paris Cedex 13 - France hudry@ Antoine Lobstein CNRS - LTCI UMR 5141 GET - Telecom Paris 46 rue Barrault 75634 Paris Cedex 13 - France lobstein@ Submitted Jan 31 2006 Accepted Dec 21 2006 Published Jan 29 2007 Mathematics Subject Classification 05C75 05C35 Key Words Graph Theory Identifying Codes Trees Paths Abstract Consider a connected undirected graph G V E a subset of vertices C c V and an integer r 1 for any vertex v 2 V let Br v denote the ball of radius r centered at v . the set of all vertices linked to v by a path of at most r edges. If for all vertices v 2 V the sets Br v C are all nonempty and different then we call C an r-identifying code. A graph admits at least one r-identifying code if and only if it is r-twin-free that is the sets Br v v 2 V are all different. We study some structural problems in r-twin-free graphs such as the existence of the path with 2r 1 vertices as a subgraph or the consequences of deleting one vertex. THE ELECTRONIC JOURNAL OF COMBINATORICS 14 2007 R16 1 1 Introduction Given a connected undirected finite graph G V E and an integer r 1 we define Br v the ball of radius r centered at v 2 V by Br v x 2 V d X v rg where d X v denotes the number of edges in any shortest path between v and x. Whenever d X v r we say that X and v r-cover each other or simply cover if there is no ambiguity . A set X c V covers a set Y c V if every vertex in Y is covered by at least one vertex in X. Two vertices vi v2 2 V such that Br vi Br v2 are called r-twins or twins. If G has no r-twins that is if 8 vi V2 2 V vi U2 Br vi Br v2 1 then we say that G is r-twin-free or twin-free. A .

TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN
Đã 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.