کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4654409 1632818 2009 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Enumeration of simple complete topological graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Enumeration of simple complete topological graphs
چکیده انگلیسی

A simple topological graph  T=(V(T),E(T))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 GG and HH are isomorphic   if HH can be obtained from GG by a homeomorphism of the sphere, and weakly isomorphic   if GG and HH have the same set of pairs of crossing edges. We prove that the number of isomorphism classes of simple complete topological graphs on nn vertices is 2Θ(n4)2Θ(n4). We also show that the number of weak isomorphism classes of simple complete topological graphs with nn vertices and n4 crossings is at least 2n(logn−O(1))2n(logn−O(1)), which improves the estimate of Harborth and Mengersen.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 30, Issue 7, October 2009, Pages 1676–1685
نویسندگان
,