کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8902866 1632394 2018 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Spanning Euler tours and spanning Euler families in hypergraphs with particular vertex cuts
ترجمه فارسی عنوان
تورهای اویلر را پوشش می دهد و خانواده های اویلر را در هیپرپارچهای با محدودیت های ویژه ای به کار می برد
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
An Euler tour in a hypergraph is a closed walk that traverses each edge of the hypergraph exactly once, while an Euler family, first defined by Bahmanian and Å ajna, is a family of closed walks that jointly traverse each edge exactly once and cannot be concatenated. In this paper, we study the notions of a spanning Euler tour and a spanning Euler family, that is, an Euler tour (family) that also traverses each vertex of the hypergraph at least once. We examine necessary and sufficient conditions for a hypergraph to admit a spanning Euler family, most notably when the hypergraph possesses a vertex cut consisting of vertices of degree two. Moreover, we characterise hypergraphs with a vertex cut of cardinality at most two that admit a spanning Euler tour (family). This result enables us to reduce the problem of existence of a spanning Euler tour (which is NP-complete), as well as the problem of a spanning Euler family, to smaller hypergraphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 341, Issue 10, October 2018, Pages 2808-2819
نویسندگان
, ,