TAILIEUCHUNG - Báo cáo toán học: "Graphs with four boundary vertices"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Graphs with four boundary vertices. | Graphs with four boundary vertices Tobias Muller Attila Pori Jean-Sebastien Serenb Submitted Feb 17 2009 Accepted Dec 17 2010 Published Jan 5 2011 Mathematics Subject Classification 05C75 Abstract A vertex v of a graph G is a boundary vertex if there exists a vertex u such that the distance in G from u to v is at least the distance from u to any neighbour of v. We give a full description of all graphs that have exactly four boundary vertices which answers a question of Hasegawa and Saito. To this end we introduce the concept of frame of a graph. It allows us to construct for every positive integer b and every possible distance-vector between b points a graph G with exactly b boundary vertices such that every graph with b boundary vertices and the same distance-vector between them is an induced subgraph of G. 1 Introduction Let G V E be a graph. A vertex v G V is a boundary vertex of G if there exists a vertex u G V such that d u v d u w for all neighbours w of v. Such a vertex u is then called a witness for v. The boundary of G is the set B G of boundary vertices of G. The notion of boundary of a graph was introduced by Chartrand et al. 2 3 and studied further by Caceres et al. 1 Hernando et al. 5 and Hasegawa and Saito 4 . In a short note 6 we gave a tight bound up to a constant factor on the order of the boundary of a graph in function of its maximum or minimum degree thereby settling a problem suggested by Hasegawa and Saito 4 . School of Mathematical Sciences Sackler Faculty of Exact Sciences Tel Aviv University Tel Aviv 69978 Israel. E-mail tobias@. Research partially supported by an ERC advanced grant. Department of Mathematics Western Kentucky University Bowling Green KY 42101 USA. E-mail . 1CNRS LIAFA Universite Denis Diderot Paris France and Department of Applied Mathematics KAM - Faculty of Mathematics and Physics Charles University Prague Czech Republic. E-mail sereni@ . cuni. cz. This author s work was partially .

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học