کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4651953 1632582 2015 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On non-traceable, non-hypotraceable, arachnoid graphs
ترجمه فارسی عنوان
در نمودار های غیر قابل ردیابی، غیر قابل تشخیص، آراکنوئید
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

Motivated by questions concerning optical networks, in 2003 Gargano, Hammar, Hell, Stacho, and Vaccaro defined the notions of spanning spiders and arachnoid graphs. A spider is a tree with at most one branch (vertex of degree at least 3). The spider is centred at the branch vertex (if there is any, otherwise it is centred at any of the vertices). A graph is arachnoid if it has a spanning spider centred at any of its vertices. Traceable graphs are obviously arachnoid, and Gargano et al. observed that hypotraceable graphs (non-traceable graphs with the property that all vertex-deleted subgraphs are traceable) are also easily seen to be arachnoid. However, they did not find any other arachnoid graphs, and asked the question whether they exist. The main goal of this paper is to answer this question in the affirmative, moreover, we show that for any prescribed graph H, there exists a non-traceable, non-hypotraceable, arachnoid graph that contains H as an induced subgraph.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 49, November 2015, Pages 621-627