کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
421016 684018 2006 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Hamiltonicity and colorings of arrangement graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Hamiltonicity and colorings of arrangement graphs
چکیده انگلیسی

We study connectivity, Hamilton path and Hamilton cycle decomposition, 4-edge and 3-vertex coloring for geometric graphs arising from pseudoline (affine or projective) and pseudocircle (spherical) arrangements. While arrangements as geometric objects are well studied in discrete and computational geometry, their graph theoretical properties seem to have received little attention so far. In this paper we show that they provide well-structured examples of families of planar and projective-planar graphs with very interesting properties. Most prominently, spherical arrangements admit decompositions into two Hamilton cycles; this is a new addition to the relatively few families of 4-regular graphs that are known to have Hamiltonian decompositions. Other classes of arrangements have interesting properties as well: 4-connectivity, 3-vertex coloring or Hamilton paths and cycles. We show a number of negative results as well: there are projective arrangements which cannot be 3-vertex colored. A number of conjectures and open questions accompany our results.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 154, Issue 17, 15 November 2006, Pages 2470–2483
نویسندگان
, , , ,