کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4646658 1342309 2016 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Uniqueness and minimal obstructions for tree-depth
ترجمه فارسی عنوان
منحصر به فرد و حداقل مانع از عمق درخت
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

A kk-ranking of a graph GG is a labeling of the vertices of GG with values from {1,…,k}{1,…,k} such that any path joining two vertices with the same label contains a vertex having a higher label. The tree-depth of GG is the smallest value of kk for which a kk-ranking of GG exists. The graph GG is kk-critical if it has tree-depth kk and every proper minor of GG has smaller tree-depth.We establish partial results in support of two conjectures about the order and maximum degree of kk-critical graphs. As part of these results, we define a graph GG to be 1-unique   if for every vertex vv in GG, there exists an optimal ranking of GG in which vv is the unique vertex with label 1. We show that several classes of kk-critical graphs are 1-unique, and we conjecture that the property holds for all kk-critical graphs. Generalizing a previously known construction for trees, we exhibit an inductive construction that uses 1-unique kk-critical graphs to generate large classes of critical graphs having a given tree-depth.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 339, Issue 2, 6 February 2016, Pages 606–613
نویسندگان
, ,