کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
5777647 1632971 2017 18 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Decomposing highly edge-connected graphs into homomorphic copies of a fixed tree
ترجمه فارسی عنوان
تجزیه گراف های متصل به لبه ها به کدهای هماهنگ با یک درخت ثابت
کلمات کلیدی
لبه تجزیه، درختان، اتصال لبه،
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
The Tree Decomposition Conjecture by Barát and Thomassen states that for every tree T there exists a natural number k(T) such that the following holds: If G is a k(T)-edge-connected simple graph with size divisible by the size of T, then G can be edge-decomposed into subgraphs isomorphic to T. So far this conjecture has only been verified for paths, stars, and a family of bistars. We prove a weaker version of the Tree Decomposition Conjecture, where we require the subgraphs in the decomposition to be isomorphic to graphs that can be obtained from T by vertex-identifications. We call such a subgraph a homomorphic copy of T. This implies the Tree Decomposition Conjecture under the additional constraint that the girth of G is greater than the diameter of T. As an application, we verify the Tree Decomposition Conjecture for all trees of diameter at most 4.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 122, January 2017, Pages 91-108
نویسندگان
,