کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5777412 1632752 2017 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Cycles through all finite vertex sets in infinite graphs
ترجمه فارسی عنوان
چرخه ها را از طریق تمام مجموعه های عددی محدود در گراف های نامحدود
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
A closed curve in the Freudenthal compactification |G| of an infinite locally finite graph G is called a Hamiltonian curve if it meets every vertex of G exactly once (and hence it meets every end at least once). We prove that |G| has a Hamiltonian curve if and only if every finite vertex set of G is contained in a cycle of G. We apply this to extend a number of results and conjectures on finite graphs to Hamiltonian curves in infinite locally finite graphs. For example, Barnette's conjecture (that every finite planar cubic 3-connected bipartite graph is Hamiltonian) is equivalent to the statement that every one-ended planar cubic 3-connected bipartite graph has a Hamiltonian curve. It is also equivalent to the statement that every planar cubic 3-connected bipartite graph with a nowhere-zero 3-flow (with no restriction on the number of ends) has a Hamiltonian curve. However, there are 7-ended planar cubic 3-connected bipartite graphs that do not have a Hamiltonian curve.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 65, October 2017, Pages 259-275
نویسندگان
, , ,