کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419164 681748 2007 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Noncrossing Hamiltonian paths in geometric graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Noncrossing Hamiltonian paths in geometric graphs
چکیده انگلیسی

A geometric graph is a graph embedded in the plane in such a way that vertices correspond to points in general position and edges correspond to segments connecting the appropriate points. A noncrossing Hamiltonian path in a geometric graph is a Hamiltonian path which does not contain any intersecting pair of edges. In the paper, we study a problem asked by Micha Perles: determine the largest number h(n)h(n) such that when we remove any set of h(n)h(n) edges from any complete geometric graph on n   vertices, the resulting graph still has a noncrossing Hamiltonian path. We prove that h(n)⩾(1/22)n. We also establish several results related to special classes of geometric graphs. Let h1(n)h1(n) denote the largest number such that when we remove edges of an arbitrary complete subgraph of size at most h1(n)h1(n) from a complete geometric graph on n   vertices the resulting graph still has a noncrossing Hamiltonian path. We prove that 12n

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 155, Issue 9, 1 May 2007, Pages 1096–1105
نویسندگان
, , , ,