کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4652939 | 1632602 | 2007 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Enumeration of simple complete topological graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
A simple topological graph T=(V(T),E(T)) is a drawing of a graph in the plane, where every two edges have at most one common point (an end-point or a crossing) and no three edges pass through a single crossing. Topological graphs G and H are isomorphic if H can be obtained from G by a homeomorphism of the sphere, and weakly isomorphic if G and H have the same set of pairs of crossing edges. We prove that the number of isomorphism classes of simple complete topological graphs on n vertices is 2Θ(n4). We also show that the number weak isomorphism classes of simple complete topological graphs with n vertices and crossings is at least 2n(logn−O(1)), which improves the estimate of Harborth an Mengersen.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 29, 15 August 2007, Pages 295-299
Journal: Electronic Notes in Discrete Mathematics - Volume 29, 15 August 2007, Pages 295-299